Submission #2710045

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

lli n,q;
vll a,b,c;
multiset<lli> l,r;
lli ans = 0;
lli p,x,y;

int main(){
  cin >> n >> q;
  a = vll(2*n);
  b = vll(2*n);
  c = vll(2*n);
  for(lli i = 0;i < 2*n;i++) cin >> a[i];
  for(lli i = 0;i < 2*n;i++) cin >> b[i];
  for(lli i = 0;i < 2*n;i++) c[i] = a[i]-b[i];
  ans = accumulate(a.begin(),a.end(),0ll);
  for(lli i = 1;i < 2*n-1;i++){
    if(c[i] < 0){
      r.insert(c[i]);
    }else{
      l.insert(c[i]);
    }
  }

  for(lli x : r){
    ans -= x;
  }
  for(lli i = 0;i < q;i++){
    cin >> p >> x >> y;
    p--;
    if(p >= 1 && p < 2*n-1){
      if(l.find(c[p]) != l.end()) l.erase(l.find(c[p]));
      else if(r.find(c[p]) != r.end()){
        r.erase(r.find(c[p]));
        ans += c[p];
      }
    }
    ans -= a[p];
    a[p] = x;
    b[p] = y;
    c[p] = a[p]-b[p];
    ans += a[p];
    if(p >= 1 && p < 2*n-1){
      if(c[p] < 0){
        r.insert(c[p]);
        ans -= c[p];
      } else l.insert(c[p]);
    }
    if(r.size()%2 == 1 && *r.rbegin()+*l.begin() < 0) cout << ans+*l.begin() << endl;
    if(r.size()%2 == 1 && *r.rbegin()+*l.begin() >= 0) cout << ans+*r.rbegin() << endl;
    else cout << ans << endl;
  }
}

Submission Info

Judge Result