Submission #2180250
Source Code Expand
#include <bits/stdc++.h> using namespace std; const int N = 200005; int n, q; int a[N], b[N]; multiset < pair<long long, int> > sa, sb; // (b - a, p) long long sum; void reset() { while(sa.size() >= 2) { multiset < pair<long long, int> > :: iterator it; it = sa.end(); --it; pair<long long, int> x = (*it); --it; pair<long long, int> y = (*it); if (x.first + y.first > 0) { sb.insert(x); sb.insert(y); sum -= a[x.second]; sum += b[x.second]; sum -= a[y.second]; sum += b[y.second]; sa.erase(sa.find(x)); sa.erase(sa.find(y)); } else break; } } void debug(multiset< pair<long long, int> > &s) { for (auto &e : s) printf("[%lld, %d] ", e.first, e.second); printf("\n"); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> q; for (int i = 1; i <= 2 * n; ++i) cin >> a[i]; for (int i = 1; i <= 2 * n; ++i) cin >> b[i]; for (int i = 1; i <= 2 * n; ++i) { sum += a[i]; if (i != 1 && i != 2 * n) { sa.insert(make_pair(b[i] - a[i], i)); } } reset(); while(q--) { int p, x, y; cin >> p >> x >> y; if (p != 1 && p != 2 * n) { if (sb.find(make_pair(b[p] - a[p], p)) != sb.end()) { sb.erase(sb.find(make_pair(b[p] - a[p], p))); sum -= b[p]; } else if (sa.find(make_pair(b[p] - a[p], p)) != sa.end()) { sa.erase(sa.find(make_pair(b[p] - a[p], p))); sum -= a[p]; } } else { sum -= a[p]; } a[p] = x; b[p] = y; sum += a[p]; if (p != 1 && p != 2 * n) sa.insert(make_pair(y - x, p)); //printf("sa "); debug(sa); //printf("sb "); debug(sb); int ndel = 0; while(!sb.empty()) { if (ndel >= 2 && sb.size() % 2 == 0) break; ++ndel; sum -= b[(*sb.begin()).second]; sum += a[(*sb.begin()).second]; sa.insert(*sb.begin()); sb.erase(sb.begin()); } reset(); //printf("sa "); debug(sa); //printf("sb "); debug(sb); printf("%lld\n", sum); } }
Submission Info
Submission Time | |
---|---|
Task | C - Paired Parentheses |
User | cheater2k |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1986 Byte |
Status | AC |
Exec Time | 417 ms |
Memory | 15872 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 300 / 300 | 200 / 200 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt |
Subtask1 | 00_example_01.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt |
Subtask2 | s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s2_24.txt, s2_25.txt, s2_26.txt, s2_27.txt, s2_28.txt |
All | 00_example_01.txt, 00_example_02.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s2_24.txt, s2_25.txt, s2_26.txt, s2_27.txt, s2_28.txt, s3_29.txt, s3_30.txt, s3_31.txt, s3_32.txt, s3_33.txt, s3_34.txt, s3_35.txt, s3_36.txt, s3_37.txt, s3_38.txt, s3_39.txt, s3_40.txt, s3_41.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 1 ms | 256 KB |
00_example_02.txt | AC | 1 ms | 256 KB |
s1_01.txt | AC | 1 ms | 256 KB |
s1_02.txt | AC | 1 ms | 256 KB |
s1_03.txt | AC | 1 ms | 256 KB |
s1_04.txt | AC | 1 ms | 256 KB |
s1_05.txt | AC | 1 ms | 256 KB |
s1_06.txt | AC | 1 ms | 256 KB |
s1_07.txt | AC | 1 ms | 256 KB |
s1_08.txt | AC | 1 ms | 256 KB |
s1_09.txt | AC | 1 ms | 256 KB |
s1_10.txt | AC | 1 ms | 256 KB |
s1_11.txt | AC | 1 ms | 256 KB |
s1_12.txt | AC | 1 ms | 256 KB |
s1_13.txt | AC | 1 ms | 256 KB |
s2_14.txt | AC | 5 ms | 896 KB |
s2_15.txt | AC | 6 ms | 1024 KB |
s2_16.txt | AC | 94 ms | 9984 KB |
s2_17.txt | AC | 72 ms | 8320 KB |
s2_18.txt | AC | 150 ms | 14336 KB |
s2_19.txt | AC | 157 ms | 14336 KB |
s2_20.txt | AC | 148 ms | 14336 KB |
s2_21.txt | AC | 151 ms | 14336 KB |
s2_22.txt | AC | 5 ms | 896 KB |
s2_23.txt | AC | 6 ms | 1024 KB |
s2_24.txt | AC | 5 ms | 896 KB |
s2_25.txt | AC | 163 ms | 14336 KB |
s2_26.txt | AC | 157 ms | 14336 KB |
s2_27.txt | AC | 155 ms | 14336 KB |
s2_28.txt | AC | 156 ms | 14336 KB |
s3_29.txt | AC | 128 ms | 7936 KB |
s3_30.txt | AC | 159 ms | 4992 KB |
s3_31.txt | AC | 134 ms | 11520 KB |
s3_32.txt | AC | 351 ms | 12416 KB |
s3_33.txt | AC | 134 ms | 7936 KB |
s3_34.txt | AC | 417 ms | 15744 KB |
s3_35.txt | AC | 411 ms | 15744 KB |
s3_36.txt | AC | 307 ms | 15744 KB |
s3_37.txt | AC | 316 ms | 15744 KB |
s3_38.txt | AC | 310 ms | 15872 KB |
s3_39.txt | AC | 315 ms | 15744 KB |
s3_40.txt | AC | 38 ms | 1024 KB |
s3_41.txt | AC | 38 ms | 1024 KB |