Submission #2474288

---

Source Code Expand

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

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, q; cin >> n >> q;
  n <<= 1;
  vector<ll> a(n), b(n);
  multiset<ll> treeone;
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) cin >> b[i];
  int use = 0;
  ll now = 0;
  for(int i = 1; i < n - 1; i++) {
    now += max(a[i], b[i]);
    if(a[i] < b[i]) use ^= 1;
    treeone.emplace(abs(a[i] - b[i]));
  }

  while(q--) {
    int i, x, y; cin >> i >> x >> y;
    i--;
    if(i == 0 || i == n - 1) {
    } else {
      now -= max(a[i], b[i]);
      if(a[i] < b[i]) use ^= 1;
      treeone.erase(treeone.lower_bound(abs(a[i] - b[i])));
      now += max(x, y);
      if(x < y) use ^= 1;
      treeone.emplace(abs(x - y));
    }
    a[i] = x; b[i] = y;
    ll ans = a[0] + a[n - 1];
    ans += now;
    if(use) ans -= *(treeone.begin());
    cout << ans << endl;
  }
}

Submission Info

Judge Result