- Translate each rule into one explicit state update.
- Maintain the invariant after every processed item.
- Return the accumulated state once all relevant input has been handled.
Code notes
- 125 lines of C++ from the credited upstream file ccc25s3.cpp.
- The implementation visibly relies on ordered lookup.
- 4 loop blocks detected.
Complexity
Count the number and nesting of passes over the input, then include the maintained containers in the memory estimate.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1234 5 6#include <bits/stdc++.h>7 8#define int long long9#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]; 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}); 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}