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
AC × 2
AC × 14
AC × 15
AC × 43
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