Submission #856044

#	Time	Username	Problem	Language	Result	Execution time	Memory
856044		mraron	Sum Zero (RMI20_sumzero)	C++14	61 / 100	244 ms	29620 KiB

sumzero

#include<bits/stdc++.h>
using namespace std;
const int MAXN=400001;
using ll = long long ;
int n;
int c[MAXN];
int q;
int qL[MAXN], qR[MAXN];
int qans[MAXN];
ll llpref[MAXN];
int pref[MAXN];
int last[MAXN];
int ans[MAXN], where[MAXN], best[MAXN];
void solve(int L, int R, vector<int>& qs) {
    //~ cerr<<L<<" "<<R<<"\n"<<flush;
    if(L==R) {
        for(auto i:qs) {
            qans[i]=c[qL[i]]==0;
        }
        return ;
    }
    if(qs.empty()) 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]);
    }
    
    vector<int> bal, jobb;
    for(int i:qs) {
        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]++;
        }else if(qR[i]<=mid) {
            bal.push_back(i);
        }else {
            jobb.push_back(i);
        }
    }  
    
    if(L<R) { 
        solve(L, mid, bal);
        solve(mid+1, R, jobb);
    }
    //~ 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) {
        cin>>c[i];
        llpref[i]=llpref[i-1]+c[i];
        lst.push_back({llpref[i], i});
    }
    lst.push_back({llpref[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;
        //~ int curr_pref=pref[i];
        //~ assert(curr_pref>=0 && curr_pref<MAXN);
    }
    
    
    cin>>q;
    for(int i=0;i<q;++i) cin>>qL[i]>>qR[i];
    
    vector<int> qs;
    for(int i=0;i<q;++i) {
        qs.push_back(i);
        qans[i]=0;
    }
    solve(1, n, qs);
    for(int i=0;i<q;++i) cout<<qans[i]<<"\n";
}

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