제출 #920530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
920530		imarn	Sum Zero (RMI20_sumzero)	C++14	22 / 100	48 ms	23984 KiB

sumzero

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#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;
vector<int>g[N];
bool vis[N]{0};
int sz[N]{0},head[N]{0},dep[N]{0},pr[N]{0},id[N]{0},rid[N]{0},cur=0;
void dfs(int u,int p,int l){
    sz[u]=1;dep[u]=l;pr[u]=p;
    for(auto v:g[u]){
        if(v==p)continue;
        dfs(v,u,l+1);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);
    }
}
int qr(int l,int r,int res=0){
    while(l<=r){
        if(pr[head[l]]<=r){
            res+=id[l]-id[head[l]]+1;
            l=pr[head[l]];
        }
        else {
            int le=id[head[l]],re=id[l];
            while(le<re){
                int m=(le+re)>>1;
                if(rid[m]<=r)re=m;
                else le=m+1;
            }res+=id[l]-le;break;
        }
    }return res;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++)cin>>a[i];
    unordered_map<int,int>um;int sum=0;
    int id=0;um[0]=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        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,0);hld(n+1,n+1,n+1);
    int q;cin>>q;
    while(q--){
        int l,r;cin>>l>>r;l--;
        cout<<qr(l,r)<<'\n';
    }
}

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