Submission #1006228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006228		imarn	Sum Zero (RMI20_sumzero)	C++14	61 / 100	178 ms	35760 KiB

sumzero

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pii>
using namespace std;
const int N=4e5+5;
int le,re,m,cnt=0,l,r,res;
vector<int>g[N];
int sz[N]{0},head[N]{0},pr[N]{0},rid[N]{0},cur=0;
void dfs(int u,int p){
    sz[u]=1;pr[u]=p;
    for(auto v:g[u]){
        if(v==p)continue;
        dfs(v,u);sz[u]+=sz[v];
    }
}
void hld(int u,int p,int tp){
    head[u]=tp;sz[u]=++cur;rid[cur]=u;
    int hv=-1,hc=-1;
    for(auto v:g[u]){
        if(v==p)continue;
        if(sz[v]>hc)hc=sz[v],hv=v;
    }if(hv==-1)return;
    hld(hv,u,tp);
    for(auto v:g[u]){
        if(v==p||v==hv)continue;
        hld(v,u,v);
    }
}
void qr(){
    res=0;
    while(l<=r){
        if(pr[head[l]]<=r){
            res+=sz[l]-sz[head[l]]+1;
            l=pr[head[l]];cnt++;
        }
        else {
            cnt++;
            le=sz[head[l]],re=sz[l];
            while(le<re){
                m=(le+re)>>1;
                if(rid[m]<=r)re=m;
                else le=m+1;
            }res+=sz[l]-le;break;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,x;cin>>n;ll sum=0;
    int id=0;vector<ll>vec;vec.pb(0);
    for(int i=1;i<=n;i++){
        cin>>rid[i];sum+=rid[i];vec.pb(sum);
    }sort(vec.begin(),vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end());sum=0;
    for(int i=0;i<=n;i++)head[i]=-1;head[lower_bound(vec.begin(),vec.end(),0)-vec.begin()]=0;
    for(int i=1;i<=n;i++){
        sum+=rid[i];
        int j=lower_bound(vec.begin(),vec.end(),sum)-vec.begin();
        if(head[j]!=-1){
            while(id<=head[j])g[i].pb(id),sz[id++]=1;
            head[j]=-1;
        }head[j]=i;
    }for(int i=0;i<=n;i++)head[i]=0,rid[i]=0;
    for(int i=0;i<=n;i++)if(!sz[i])g[n+1].pb(i),sz[i]=1;
    dfs(n+1,n+1);hld(n+1,n+1,n+1);
    int q;cin>>q;
    while(q--){
        cin>>l>>r;l--;
        qr();cout<<res<<'\n';
    }
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:62:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   62 |     for(int i=0;i<=n;i++)head[i]=-1;head[lower_bound(vec.begin(),vec.end(),0)-vec.begin()]=0;
      |     ^~~
sumzero.cpp:62:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   62 |     for(int i=0;i<=n;i++)head[i]=-1;head[lower_bound(vec.begin(),vec.end(),0)-vec.begin()]=0;
      |                                     ^~~~
sumzero.cpp:57:11: warning: unused variable 'x' [-Wunused-variable]
   57 |     int n,x;cin>>n;ll sum=0;
      |           ^

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