제출 #928840

#제출 시각아이디문제언어결과실행 시간메모리
928840winter0101Sum Zero (RMI20_sumzero)C++14
61 / 100
370 ms56380 KiB
#include<bits/stdc++.h> using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define pii pair<int,int> #define pli pair<long long,int> #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) #define pil pair<int,long long> const int maxn=4e5+9; long long a[maxn]; int nxt[maxn]; int st[maxn][21]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen("temp.INP","r",stdin); //freopen("temp.OUT","w",stdout); int n; cin>>n; for1(i,1,n){ cin>>a[i]; a[i]+=a[i-1]; } map<long long,int>f; for2(i,n,1){ f[a[i]]=i; if (f.find(a[i-1])!=f.end()){ nxt[i]=f[a[i-1]]; } else nxt[i]=n+1; } for2(i,n-1,1)nxt[i]=min(nxt[i],nxt[i+1]); //for1(i,1,n)cout<<nxt[i]<<'\n'; for1(i,1,n)st[i][0]=nxt[i]; for1(j,1,20){ for1(i,1,n){ if (st[i][j-1]+1>n){ st[i][j]=n+1; continue; } st[i][j]=st[st[i][j-1]+1][j-1]; } } int q; cin>>q; for1(i,1,q){ int l,r; cin>>l>>r; int ans=0; for2(j,20,0){ if (l>r)break; if (st[l][j]<=r){ ans+=(1<<j); l=st[l][j]+1; } } cout<<ans<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...