제출 #856072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856072		mraron	Sum Zero (RMI20_sumzero)	C++14	61 / 100	313 ms	21268 KiB

sumzero

#include<bits/stdc++.h>
using namespace std;
const int MAXN=400001;
using ll = long long ;
int n;
int q;
int qL[MAXN], qR[MAXN], qs[MAXN];
int qans[MAXN];
ll pref[MAXN];
int last[MAXN];
int ans[MAXN], where[MAXN], best[MAXN];
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];
            qans[i]=pref[qL[i]]==pref[qL[i]-1];
        }
        return ;
    }
    if(ql>qr) return ;
    int mid=(L+R)/2;

    auto 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;
    };
    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]) {
            qans[i]=ans[qL[i]-1]+ans[qR[i]];
            int leftStop=where[qL[i]-1], rightStart=where[qR[i]];
            if(leftStop<=best[rightStart]) qans[i]++;
        }
    }  
    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;
            }
        }
    }
    
    for(int i=ql;i<bal;++i) assert(qR[qs[i]]<=mid);
    for(int i=jobb+1;i<=qr;++i) assert(qL[qs[i]]>=mid+1);
    
    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;
        for(int i=1;i<=n;++i) {
            int c;
            cin>>c;
            pref[i]=pref[i-1]+c;
            lst.push_back({pref[i], i});
        }
        lst.push_back({pref[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;
        }
    }
    
    
    cin>>q;
    for(int i=0;i<q;++i) cin>>qL[i]>>qR[i];
    
    for(int i=0;i<q;++i) {
        qs[i]=i;
        qans[i]=0;
    }
    solve(1, n, 0, q-1);
    for(int i=0;i<q;++i) cout<<qans[i]<<"\n";
}

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