제출 #856035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856035		mraron	Sum Zero (RMI20_sumzero)	C++17	61 / 100	1052 ms	40708 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];

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;
    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, bool left) {
        #define chkmx(ind, val, ww) if(ans[ind]<val || (ans[ind]==val && abs(mid-ww)>abs(mid-where[ind]))) {ans[ind]=val;where[ind]=ww;}
        int ind=i-(L-1);
        ans[ind]=0;
        where[ind]=i;
        if(left && i+1<=mid) {
            chkmx(ind, ans[ind+1], where[ind+1]);
        }
        if(!left && i-1>=mid+1) {
            chkmx(ind, ans[ind-1], where[ind-1]);
        }
        
        ll curr_pref=pref[ind];
        if(last.count(curr_pref)) {
            int w=last[curr_pref];
            chkmx(ind, (1+ans[w]), where[w]);
        }
        
        last[curr_pref]=ind;
    };
    for(int i=mid;i>=L-1;i--) {
        handle(i, true);
    }
    last.clear();
    for(int i=mid+1;i<=R;i++) {
        handle(i, false);
    }
    
    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(ind>0) 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-(L-1)]+ans[qR[i]-(L-1)];
            int leftStop=where[qL[i]-1-(L-1)], rightStart=where[qR[i]-(L-1)];
            if(leftStop<=best[rightStart-(mid+1)]) 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;
    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);
        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