Submission #3150759

---

Source Code Expand

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

using ll=long long;

int main(){
    int n;
    int q;
    cin>>n>>q;

    vector<ll> a(2*n),b(2*n);
    for(int i=0;i<2*n;i++) cin>>a[i];
    for(int i=0;i<2*n;i++) cin>>b[i];
    
    ll psum=0;
    ll bsum=0;
    multiset<ll> ps;
    multiset<ll> ns;
    for(int i=1;i<2*n-1;i++){
        bsum+=b[i];
        if(a[i]-b[i]>=0){
            ps.insert(a[i]-b[i]);
            psum+=a[i]-b[i];
        }
        else ns.insert(a[i]-b[i]);
    }
    
    while(q--){
        int p;
        ll ax,bx;
        cin>>p>>ax>>bx;
        p--;
        if(p==0 || p==2*n-1){
            a[p]=ax;
            b[p]=bx;
        }
        else{
            bsum+=bx-b[p];
            if(a[p]-b[p]>=0){
                ps.erase(ps.find(a[p]-b[p]));
                psum-=a[p]-b[p];
            }
            else{
                ns.erase(ns.find(a[p]-b[p]));
            }
            a[p]=ax,b[p]=bx;
            if(a[p]-b[p]>=0){
                ps.insert(a[p]-b[p]);
                psum+=a[p]-b[p];
            }
            else ns.insert(a[p]-b[p]);
        }
        if(n==1){
            cout<<a[0]+a[1]<<endl;
        }
        else if(ns.size()%2){
            ll vp=*ps.begin();
            ll vn=*(--ns.end());
            cout<<a[0]+a[2*n-1]+bsum+psum+max(-vp,vn)<<endl;
        }   
        else{
            cout<<a[0]+a[2*n-1]+psum+bsum<<endl;
        }                 
    }


    return 0;
}

Submission Info

Judge Result