This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define fir first
#define sec second
#define mod 998244353
#define int long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
typedef pair<int,int> pii;
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 400005
int pre[N];
signed a[N],to[N],n,Q;
vector<signed> G[N];
map<int,int> vis;
signed dep[N],siz[N],son[N],fa[N],top[N],dfn[N],id[N],dfscnt;
void dfs1(int u,int f)
{
fa[u]=f,dep[u]=dep[f]+1,siz[u]=1;
for(int v:G[u])
{
dfs1(v,u),siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int tp)
{
top[u]=tp,dfn[u]=++dfscnt,id[dfscnt]=u;
if(son[u]) dfs2(son[u],tp);
for(int v:G[u]) if(v!=son[u]) dfs2(v,v);
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
for(int i=n;i>=1;i--)
{
vis[pre[i]]=i+1;
if(!vis[pre[i-1]]) to[i]=n+2;
else to[i]=vis[pre[i-1]];
}
vis.clear();
to[n+1]=n+2,to[n+2]=n+2;
for(int i=n;i>=1;i--) to[i]=min(to[i],to[i+1]);
for(int i=1;i<=n+1;i++) G[to[i]].pb(i);
dfs1(n+2,n+2),dfs2(n+2,n+2);
// for(int i=1;i<=n+2;i++) print(G[i]);
// for(int i=1;i<=n+2;i++) printf("%d %d\n",i,fa[i]);
// for(int i=1;i<=n+2;i++) printf("%d%c",id[i]," \n"[i==n+2]);
cin>>Q;
while(Q--)
{
int l=read(),r=read()+1,ans=0;
while(fa[top[l]]<=r) ans+=dep[top[l]]-dep[l]+1,l=fa[top[l]];
// printf("^ %d %d\n",l,ans);
int R=dfn[l],L=dfn[top[l]],res=0;
// printf("%d %d\n",L,R);
while(L<=R)
{
int mid=(L+R)/2;
if(id[mid]<=r) R=mid-1,res=dfn[l]-mid;
else L=mid+1;
}
printf("%lld\n",ans+res);
}
return 0;
}
Compilation message (stderr)
sumzero.cpp: In function 'void print(std::vector<long long int>)':
sumzero.cpp:23:69: warning: format '%d' expects argument of type 'int', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} [-Wformat=]
23 | void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
| ~^
| |
| int
| %lld
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |