Submission #1224430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224430		tosivanmak	Fish 2 (JOI22_fish2)	C++20	100 / 100	1516 ms	52432 KiB

fish2

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

ll arr[100005];
struct info{
    ll l,r,exsum,ppl;
};

void norm_pref(vector<info>& a){
    if(a.size()<=1)return;
    if(a[a.size()-1].r!=a[a.size()-2].r)return;
    ll cur=a[a.size()-1].ppl;
    a.pop_back();
    a[a.size()-1].ppl+=cur;
}
void norm_suff(vector<info>& a){
    if(a.size()<=1)return;
    if(a[a.size()-1].l!=a[a.size()-2].l)return;
    ll cur=a[a.size()-1].ppl;
    a.pop_back();
    a[a.size()-1].ppl+=cur;
}
void merge_pref(vector<info>& a, vector<info> b){
    vector<info>k;
    ll ptr=0,ptr2=0;
    while(ptr<a.size()&&ptr2<b.size()){
        if(a[ptr].r<b[ptr2].r){k.push_back(a[ptr]); ptr++;}
        else{k.push_back(b[ptr2]); ptr2++;}
        norm_pref(k);
    }
    if(ptr<a.size()){
        for(int i=ptr;i<a.size();i++){
            k.push_back(a[i]); norm_pref(k);
        }
    }
    else{
        for(int i=ptr2;i<b.size();i++){
            k.push_back(b[i]); norm_pref(k);
        }
    }
    a.swap(k);
}
void merge_suff(vector<info>& a, vector<info> b){
    vector<info>k;
    ll ptr=0,ptr2=0;
    while(ptr<a.size()&&ptr2<b.size()){
        if(a[ptr].l>b[ptr2].l){k.push_back(a[ptr]); ptr++;}
        else{k.push_back(b[ptr2]); ptr2++;}
        norm_suff(k);
    }
    if(ptr<a.size()){
        for(int i=ptr;i<a.size();i++){
            k.push_back(a[i]); norm_suff(k);
        }
    }
    else{
        for(int i=ptr2;i<b.size();i++){
            k.push_back(b[i]); norm_suff(k);
        }
    }
    a.swap(k);
}
void normalize(vector<info>& a){
    for(int i=a.size()-1;i>=1;i--){
        a[i].exsum-=a[i-1].exsum;
    }
}
struct node{
    vector<info>pref; vector<info>suff;
    void set(ll pos, ll val){
        pref.clear(); suff.clear();
        pref.push_back({pos,pos,val,1}); suff.push_back({pos,pos,val,1});
    }
    node operator+(const node& nd)const{
        // 2-ptr
        // merge my suff and nd's pref 
        vector<info>npref,nsuff,nnpref,nnsuff,rpref,rsuff;
        rpref=pref; rsuff=nd.suff;
        for(int i=1;i<rpref.size();i++){
            rpref[i].exsum+=rpref[i-1].exsum;
        }
        for(int i=1;i<rsuff.size();i++){
            rsuff[i].exsum+=rsuff[i-1].exsum;
        }
        rpref.pop_back(); rsuff.pop_back();
        ll ptrme=0,ptrhim=-1,cursum=suff[0].exsum;
        for(int i=0;i<suff.size();i++){
            while(ptrme<i){
                ptrme++; cursum+=suff[ptrme].exsum;
            }
            while(1){
                if(ptrme+1<suff.size()){
                    if(cursum>=arr[suff[ptrme].l-1]){
                        ptrme++; cursum+=suff[ptrme].exsum;
                        continue;
                    }
                }
                if(ptrhim+1<nd.pref.size()){
                    if(ptrhim==-1){
                        if(cursum>=arr[nd.pref[ptrhim+1].l]){
                            ptrhim++; cursum+=nd.pref[ptrhim].exsum;
                            continue;
                        }
                    }
                    else{
                        if(cursum>=arr[nd.pref[ptrhim].r+1]){
                            ptrhim++; cursum+=nd.pref[ptrhim].exsum;
                            continue;
                        }
                    }
                }
                break;
            }
            if(ptrme==(int)suff.size()-1){
                if(ptrhim==-1){
                    npref.push_back({suff[ptrme].l,suff[ptrme].r,cursum,suff[i].ppl});
                }
                else{
                    npref.push_back({suff[suff.size()-1].l,nd.pref[ptrhim].r,cursum,suff[i].ppl});
                }
            }
            if(ptrhim==(int)nd.pref.size()-1){
                nsuff.push_back({suff[ptrme].l,nd.pref[ptrhim].r,cursum,suff[i].ppl});
            }
        }


        ptrme=-1,ptrhim=0,cursum=nd.pref[0].exsum;
        for(int i=0;i<nd.pref.size();i++){
            while(ptrhim<i){
                ptrhim++; cursum+=nd.pref[ptrhim].exsum;
            }
            while(1){
                if(ptrhim+1<nd.pref.size()){
                    if(cursum>=arr[nd.pref[ptrhim].r+1]){
                        ptrhim++; cursum+=nd.pref[ptrhim].exsum;
                        continue;
                    }
                }
                if(ptrme+1<suff.size()){
                    if(ptrme==-1){
                        if(cursum>=arr[suff[ptrme+1].r]){
                            ptrme++; cursum+=suff[ptrme].exsum;
                            continue;
                        }
                    }
                    else{
                        if(cursum>=arr[suff[ptrme].l-1]){
                            ptrme++; cursum+=suff[ptrme].exsum;
                            continue;
                        }
                    }
                }
                break;
            }
            if(ptrhim==(int)nd.pref.size()-1){
                if(ptrme==-1){
                    nnsuff.push_back({nd.pref[ptrhim].l,nd.pref[ptrhim].r,cursum,nd.pref[i].ppl});
                }
                else{
                    nnsuff.push_back({suff[ptrme].l,nd.pref[ptrhim].r,cursum,nd.pref[i].ppl});
                }
            }
            if(ptrme==(int)suff.size()-1){
                nnpref.push_back({suff[ptrme].l,nd.pref[ptrhim].r,cursum,nd.pref[i].ppl});
            }
        }
        merge_pref(rpref,npref); merge_pref(rpref,nnpref);
        merge_suff(rsuff,nsuff); merge_suff(rsuff,nnsuff);
        normalize(rsuff); normalize(rpref);
        return {rpref,rsuff};
    }
};

struct SEG{
    vector<node>seg;
    vector<ll>a;
    void init(ll n){
        seg.resize(4*n+5); a.resize(n+5);
    }
    void build(ll l, ll r, ll id){
        if(l==r){
            seg[id].set(l,a[l]); return;
        }
        ll mid=(l+r)>>1;
        build(l,mid,id*2); build(mid+1,r,id*2+1);
        seg[id]=seg[id*2]+seg[id*2+1];
    }
    void upd(ll ul, ll l, ll r, ll val, ll id){
        if(l==r){
            seg[id].set(l,val); return;
        }
        ll mid=(l+r)>>1;
        if(ul<=mid)upd(ul,l,mid,val,id*2);
        else upd(ul,mid+1,r,val,id*2+1);
        seg[id]=seg[id*2]+seg[id*2+1];
    }
    node qry(ll ql, ll qr, ll l, ll r, ll id){
        if(l>=ql&&r<=qr){
            return seg[id];
        }
        ll mid=(l+r)>>1;
        node ans;
        if(l>qr||mid<ql)return qry(ql,qr,mid+1,r,id*2+1);
        else ans=qry(ql,qr,l,mid,id*2);
        if(mid+1>qr||r<ql)return ans;
        else ans=ans+qry(ql,qr,mid+1,r,id*2+1);
        return ans;
    }
}st;

ll val(node nd){
    ll sz=nd.pref.size();
    return nd.pref[sz-1].ppl;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>arr[i];
    st.init(n);
    for(int i=1;i<=n;i++)st.a[i]=arr[i];
    st.build(1,n,1);
    ll q; cin>>q;
    while(q--){
        ll tp;
        cin>>tp;
        if(tp==1){
            ll x,y;
            cin>>x>>y; arr[x]=y;
            st.upd(x,1,n,y,1);
        }
        else{
            ll l,r;
            cin>>l>>r;
            cout<<val(st.qry(l,r,1,n,1))<<'\n';
        }
    } 
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17