oj.uz

Submission #856095

# Submission time Handle Problem Language Result Execution time Memory
856095 2023-10-02T16:34:39 Z mraron Sum Zero (RMI20_sumzero) C++14
100 / 100
 251 ms 15064 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 60 ms 13264 KB Output is correct
8 Correct 46 ms 13520 KB Output is correct
9 Correct 45 ms 13200 KB Output is correct
10 Correct 67 ms 13188 KB Output is correct
11 Correct 42 ms 13092 KB Output is correct
12 Correct 47 ms 13292 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 60 ms 13264 KB Output is correct
8 Correct 46 ms 13520 KB Output is correct
9 Correct 45 ms 13200 KB Output is correct
10 Correct 67 ms 13188 KB Output is correct
11 Correct 42 ms 13092 KB Output is correct
12 Correct 47 ms 13292 KB Output is correct
13 Correct 251 ms 14804 KB Output is correct
14 Correct 188 ms 14552 KB Output is correct
15 Correct 183 ms 15064 KB Output is correct
16 Correct 247 ms 14804 KB Output is correct
17 Correct 167 ms 14552 KB Output is correct
18 Correct 185 ms 15036 KB Output is correct