Submission #2180089

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

int n, q;
int a[N], b[N];
multiset<long long> ms;
long long sum;

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) ms.insert(b[i] - a[i]);
	}

	while(q--) {
		int p, x, y; cin >> p >> x >> y;
		sum -= a[p];
		sum += x;
		if (p != 1 && p != 2 * n) {
			ms.erase(ms.find(b[p] - a[p]));
			ms.insert(y - x);
		}
		a[p] = x;
		b[p] = y;

		multiset<long long> ns = ms;
		long long nsum = sum;
		while(ns.size() > 1) {
			long long k = (*ns.rbegin()); ns.erase(--ns.end());
			long long l = (*ns.rbegin()); ns.erase(--ns.end());

			if (k + l > 0) {
				nsum += k + l;
			} else break;
		}

		printf("%lld\n", nsum);
	}
}

Submission Info

Judge Result