Submission #2078224
Source Code Expand
#include <iostream> #include <queue> #include <functional> #include <algorithm> #include <cmath> using namespace std; long long n, q, p1, p2, p3, a[200009], b[200009], sum, cnt; priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>Q; int main() { 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++) { if (i == 1)b[i] = -(1LL << 60); if (i == 2 * n) b[i] = -(1LL << 60); sum += max(a[i], b[i]); if (a[i] < b[i]) cnt++; Q.push(make_pair(max(a[i], b[i]) - min(a[i], b[i]), i)); } for (int i = 1; i <= q; i++) { cin >> p1 >> p2 >> p3; if (p1 == 1) p3 = -(1LL << 60); if (p1 == 2 * n) p3 = -(1LL << 60); if (a[p1] < b[p1]) cnt--; sum -= max(a[p1], b[p1]); a[p1] = p2; b[p1] = p3; if (a[p1] < b[p1]) cnt++; sum += max(a[p1], b[p1]); Q.push(make_pair(abs(a[p1] - b[p1]), p1)); while (!Q.empty()) { long long cost = Q.top().first, to = Q.top().second; long long V = abs(a[to] - b[to]); if (V != cost) Q.pop(); else break; } if (cnt % 2 == 0) cout << sum << endl; else cout << sum - Q.top().first << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Paired Parentheses |
User | E869120 |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1232 Byte |
Status | AC |
Exec Time | 462 ms |
Memory | 14444 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 | 2 ms | 256 KB |
s2_14.txt | AC | 8 ms | 768 KB |
s2_15.txt | AC | 8 ms | 768 KB |
s2_16.txt | AC | 90 ms | 7920 KB |
s2_17.txt | AC | 74 ms | 4212 KB |
s2_18.txt | AC | 129 ms | 9456 KB |
s2_19.txt | AC | 130 ms | 8688 KB |
s2_20.txt | AC | 130 ms | 8944 KB |
s2_21.txt | AC | 136 ms | 9328 KB |
s2_22.txt | AC | 7 ms | 768 KB |
s2_23.txt | AC | 8 ms | 768 KB |
s2_24.txt | AC | 7 ms | 768 KB |
s2_25.txt | AC | 173 ms | 9200 KB |
s2_26.txt | AC | 174 ms | 8432 KB |
s2_27.txt | AC | 176 ms | 7664 KB |
s2_28.txt | AC | 174 ms | 7664 KB |
s3_29.txt | AC | 143 ms | 4464 KB |
s3_30.txt | AC | 218 ms | 4080 KB |
s3_31.txt | AC | 113 ms | 8432 KB |
s3_32.txt | AC | 367 ms | 7916 KB |
s3_33.txt | AC | 146 ms | 4464 KB |
s3_34.txt | AC | 397 ms | 13548 KB |
s3_35.txt | AC | 400 ms | 14060 KB |
s3_36.txt | AC | 462 ms | 14188 KB |
s3_37.txt | AC | 457 ms | 13932 KB |
s3_38.txt | AC | 455 ms | 12908 KB |
s3_39.txt | AC | 458 ms | 14444 KB |
s3_40.txt | AC | 253 ms | 1024 KB |
s3_41.txt | AC | 261 ms | 1024 KB |