2025 S3 - Pretty Pens

1// This solution was submitted in-contest. 
2// However, it uses multisets which is exclusive to C++.
3// Please upload a solution in the forum if you have a more elegant way to solve this problem.
4
5
6#include <bits/stdc++.h>
7
8#define int long long
9#define pii pair<long long, long long>
10
11using namespace std;
12
13int n, m, q;
14
15set<pair<int, int>, greater<pair<int, int>>> colors[200001];
16
17int where[200001], pretty[200001]; //where[i] is which set the ith pen is in
18
19int totalsum = 0;
20
21set<pair<int, int>> row1, row2;
22
23pii colfirst, colsecond;
24
25
26void changeColor(int id, int c) {
27    int loc = where[id];
28    int score = pretty[id];
29
30
31    colfirst = *colors[loc].begin();
32    colsecond = *(++colors[loc].begin());
33    row1.erase(colfirst);
34    row2.erase(colsecond);
35    totalsum -= colfirst.first;
36
37    colfirst = *colors[c].begin();
38    colsecond = *(++colors[c].begin());
39    row1.erase(colfirst);
40    row2.erase(colsecond);
41    totalsum -= colfirst.first;
42
43
44
45
46    colors[loc].erase({score, id});
47    colors[c].insert({score, id});
48    where[id] = c;
49
50
51
52    colfirst = *colors[loc].begin();
53    colsecond = *(++colors[loc].begin());
54    row1.insert(colfirst);
55    row2.insert(colsecond);
56    totalsum += colfirst.first;
57
58    colfirst = *colors[c].begin();
59    colsecond = *(++colors[c].begin());
60    row1.insert(colfirst);
61    row2.insert(colsecond);
62    totalsum += colfirst.first;
63}
64
65void changePretty(int id, int p) {
66    int loc = where[id];
67    int score = pretty[id];
68
69
70    colfirst = *colors[loc].begin();
71    colsecond = *(++colors[loc].begin());
72    row1.erase(colfirst);
73    row2.erase(colsecond);
74    totalsum -= colfirst.first;
75
76
77    colors[loc].erase({score, id});
78    colors[loc].insert({p, id});
79    pretty[id] = p;
80
81    colfirst = *colors[loc].begin();
82    colsecond = *(++colors[loc].begin());
83    row1.insert(colfirst);
84    row2.insert(colsecond);
85    totalsum += colfirst.first;
86}
87
88
89signed main() {
90    cin >> n >> m >> q;
91    for (int i=1; i<=m; i++) {
92        colors[i].insert({0, 0}); //out of bounds
93    }
94
95    for (int i=1; i<=n; i++) {
96        int c, p; cin >> c >> p;
97        where[i] = c;
98        pretty[i] = p;
99        colors[c].insert({p, i});
100    }
101
102    for (int i=1; i<=m; i++) {
103        totalsum += colors[i].begin()->first;
104        row1.insert(*colors[i].begin());
105        row2.insert(*(++colors[i].begin()));
106    }
107
108    cout << max(totalsum, totalsum + (--row2.end())->first - row1.begin()->first) << endl;
109
110
111    while (q--) {
112        int typ; cin >> typ;
113        int id, x; cin >> id >> x;
114
115
116        if (typ == 1) {
117            changeColor(id, x);
118        }
119        else {
120            changePretty(id, x);
121        }
122
123        cout << max(totalsum, totalsum + (--row2.end())->first - row1.begin()->first) << endl;
124    }
125}