Submission #856008

#	Time	Username	Problem	Language	Result	Execution time	Memory
856008		mraron	Sum Zero (RMI20_sumzero)	C++14	0 / 100	4 ms	1484 KiB

sumzero

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5001;
using ll = long long ;
int n;
int c[MAXN];
int q;
int qL[MAXN], qR[MAXN];
int qans[MAXN];

void solve(int L, int R, vector<int>& qs) {
    if(R<L || qs.empty()) return ;
    int mid=(L+R)/2;
    vector<int> ans(R-L+2), where(R-L+2);
    vector<ll> pref(R-L+2);
    for(int i=L;i<=R;++i) {
        pref[i-L+1]=pref[i-L]+c[i];
    }
    map<ll,int> last;
    auto handle=[&](int i) {
        ans[i]=0;
        where[i]=i;
        if(i+1<=mid) {
            if(ans[i]<ans[i+1]) {
                ans[i]=ans[i+1];
                where[i]=where[i+1];
            }
        }
        ll curr_pref=pref[i-(L-1)];
        if(last.count(curr_pref)) {
            int w=last[curr_pref];
            if(ans[i]<1+ans[w]) {
                ans[i]=1+ans[w];
                where[i]=where[w];
            }
        }
        
        last[curr_pref]=i;
    };
    for(int i=mid;i>=L-1;i--) {
        handle(i);
    }
    last.clear();
    for(int i=mid+1;i<=R;i++) {
        handle(i);
    }
    
    last.clear();
    for(int i=L-1;i<=mid;++i) {
        last[pref[i-(L-1)]]=i;
    }
    
    vector<int> best(R-(mid+1)+1);
    for(int i=mid+1;i<=R;++i) {
        int ind=i-(mid+1);
        best[ind]=-1;
        ll curr_pref=pref[i-(L-1)];
        if(last.count(curr_pref)) {
            best[ind]=last[curr_pref];
        }
        if(i>mid+1) best[ind]=max(best[ind], best[ind-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]];
            //~ cerr<<leftStop<<" "<<rightStart<<" "<<best[rightStart-(mid+1)]<<"\n";
            if(leftStop<=best[rightStart-(mid+1)]) qans[i]++;
        }else if(qR[i]<=mid) {
            bal.push_back(i);
        }else {
            jobb.push_back(i);
        }
    }   
    
    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;
    for(int i=1;i<=n;++i) cin>>c[i];
    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);
    solve(1, n, qs);
    for(int i=0;i<q;++i) cout<<qans[i]<<"\n";
}

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