제출 #928973

#제출 시각아이디문제언어결과실행 시간메모리
928973fdnfksdSum Zero (RMI20_sumzero)C++14
61 / 100
859 ms23716 KiB
#include<bits/stdc++.h> #define pb push_back #define pli pair<int,int> #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); using namespace std; using ll=long long; const ll maxn=4e5+5; const ll inf=1e18; const ll mod=1e9+7; ll n,a[maxn]; map<ll,ll>mp; int nxt[maxn],mn[maxn],p[maxn],jump[maxn],val[maxn]; const ll block=632; void solve() { cin >> n; for(int i=1;i<=n;i++) cin >> a[i],a[i]+=a[i-1]; mp[a[n]]=n; for(int i=n-1;i>=0;i--) { if(mp[a[i]]==0) nxt[i+1]=n+1; else nxt[i+1]=mp[a[i]]; mp[a[i]]=i; } nxt[n+1]=n+1; mn[n+1]=n+1; for(int i=n;i>=1;i--) { if(nxt[i]<nxt[mn[i+1]]) mn[i]=i; else mn[i]=mn[i+1]; } for(int i=n;i>=1;i--) { ll u=nxt[i]; if(u==n+1) p[i]=n+1; else u++,p[i]=mn[u]; } p[n+1]=n+1; for(int i=1;i<=n;i++) { ll cnt=0; ll u=i; while(cnt<block) { u=p[u]; cnt++; if(u==n+1) break; } jump[i]=u; val[i]=cnt; } ll q; cin >> q; for(int i=1;i<=q;i++) { int l,r; cin >> l >> r; l=mn[l]; if(nxt[l]>r) {cout << 0 << '\n';continue;} else { ll ans=1; while(nxt[jump[l]]<=r) { ans+=val[l]; l=jump[l]; } while(nxt[p[l]]<=r) { ans++; l=p[l]; } cout << ans << '\n'; } } } int main() { fastio //freopen(TASKNAME".INP","r",stdin); //freopen(TASKNAME".OUT","w",stdout); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...