Submission #856095

#	Time	Username	Problem	Language	Result	Execution time	Memory
856095		mraron	Sum Zero (RMI20_sumzero)	C++14	100 / 100	251 ms	15064 KiB

sumzero

#include<iostream>
#include<functional>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=400001;
using ll = long long ;
int n;
int q;
int qL[MAXN], qR[MAXN], qs[MAXN];
int pref[MAXN];
int last[MAXN];
int ans[MAXN], where[MAXN], best[MAXN];
int mid;

void handle(int i, bool left) {
    #define chkmx(val, ww) if(ans[i]<val || (ans[i]==val && abs(mid-ww)>abs(mid-where[i]))) {ans[i]=val;where[i]=ww;}
    
    ans[i]=0;
    where[i]=i;
    if(left && i+1<=mid) {
        chkmx(ans[i+1], where[i+1]);
    }
    if(!left && i-1>=mid+1) {
        chkmx(ans[i-1], where[i-1]);
    }
    
    int curr_pref=pref[i];
    if(last[curr_pref]!=-1) {
        int w=last[curr_pref];
        chkmx((1+ans[w]), where[w]);
    }
    
    last[curr_pref]=i;
}

void solve(int L, int R, int ql, int qr) {
    //~ cerr<<L<<" "<<R<<"\n"<<flush;
    if(L==R) {
        for(int j=ql;j<=qr;++j) {
            int i=qs[j];
            qR[i]=(pref[qL[i]]==pref[qL[i]-1])+int(1e9);
        }
        return ;
    }
    if(ql>qr) return ;
    mid=(L+R)/2;

    for(int i=R;i>=L-1;i--) {
        last[pref[i]]=-1;
    }
    for(int i=mid;i>=L-1;i--) {
        handle(i, true);
    }
    for(int i=mid;i>=L-1;i--) {
        last[pref[i]]=-1;
    }
    for(int i=mid+1;i<=R;i++) {
        handle(i, false);
    }
    for(int i=mid+1;i<=R;i++) {
        last[pref[i]]=-1;
    }
    for(int i=L-1;i<=mid;++i) {
        last[pref[i]]=i;
    }
    
    for(int i=mid+1;i<=R;++i) {
        best[i]=-1;
        int curr_pref=pref[i];
        if(last[curr_pref]!=-1) {
            best[i]=last[curr_pref];
        }
        if(i>mid+1) best[i]=max(best[i], best[i-1]);
    }
    
    for(int j=ql;j<=qr;++j) {
        int i=qs[j];
        if(qL[i]<=mid && mid+1<=qR[i]) {
            int res;
            res=ans[qL[i]-1]+ans[qR[i]];
            int leftStop=where[qL[i]-1], rightStart=where[qR[i]];
            if(leftStop<=best[rightStart]) res++;
            qR[i]=res+1e9;
        }
    }  
    int bal=ql, jobb=qr;
    for(int j=ql;j<=qr;++j) {
        bool ok=true;
        while(ok) {
            ok=false;
            while(bal<=j && qR[qs[j]]<=mid) {
                swap(qs[bal++], qs[j]);
                ok=true;
            }
            while(j<=jobb && mid+1<=qL[qs[j]]) {
                swap(qs[jobb--], qs[j]);
                ok=true;
            }
        }
    }
    
    if(L<R) { 
        solve(L, mid, ql, bal-1);
        solve(mid+1, R, jobb+1, qr);
    }
    //~ for(auto i:pref) cerr<<i<<" ";cerr<<"\n";
    //~ for(auto i:ans) cerr<<i<<" ";cerr<<"\n";
    //~ for(auto i:where) cerr<<i<<" ";cerr<<"\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    {
        vector<pair<ll,int>> lst(n+1);int ind=0;
        for(int i=1;i<=n;++i) {
            int c;
            cin>>c;
            lst[ind]={(i==1?0:lst[ind-1].first)+c, i};
            ind++;
        }
        lst[ind++]={0, 0};
        
        sort(lst.begin(), lst.end());
        pref[lst[0].second]=0;
        for(int i=1;i<(int)lst.size();++i) {
            pref[lst[i].second]=pref[lst[i-1].second];
            if(lst[i].first>lst[i-1].first) pref[lst[i].second]++;
        }
        
        for(int i=0;i<=n;++i) {
            last[pref[i]]=-1;
        }
        
        vector<pair<ll,int>>().swap(lst);
    }
    
    
    cin>>q;
    for(int i=0;i<q;++i) cin>>qL[i]>>qR[i];
    
    for(int i=0;i<q;++i) {
        qs[i]=i;
    }
    solve(1, n, 0, q-1);
    for(int i=0;i<q;++i) cout<<qR[i]-int(1e9)<<"\n";
}

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 39 / 39