제출 #920546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
920546		imarn	Sum Zero (RMI20_sumzero)	C++14	22 / 100	48 ms	22280 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];
bool vis[N]{0};
int sz[N]{0},head[N]{0},pr[N]{0},id[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;id[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(){
    cnt=0;res=0;
    while(l<=r){
        if(pr[head[l]]<=r){
            res+=id[l]-id[head[l]]+1;
            l=pr[head[l]];cnt++;
        }
        else {
            cnt++;
            le=id[head[l]],re=id[l];
            while(le<re){
                m=(le+re)>>1;
                if(rid[m]<=r)re=m;
                else le=m+1;
            }res+=id[l]-le;break;
        }
        if(cnt>50)break;
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,x;cin>>n;
    unordered_map<int,int>um;int sum=0;
    int id=0;um[0]=0;
    for(int i=1;i<=n;i++){
        cin>>x;sum+=x;
        if(um.find(sum)!=um.end()){
            while(id<=um[sum])g[i].pb(id),vis[id++]=1;
        }um[sum]=i;
    }
    for(int i=0;i<=n;i++)if(!vis[i])g[n+1].pb(i);
    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';
    }
}

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