제출 #942679

#제출 시각아이디문제언어결과실행 시간메모리
942679fdnfksdSum Zero (RMI20_sumzero)C++14
61 / 100
390 ms21064 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+100; const ll inf=1e18; const ll mod=1e9+7; ll n; pli a[maxn]; int nxt[maxn],mn[maxn],p[maxn][8],pw[10]; void solve() { cin >> n; for(int i=1;i<=n;i++) cin >> a[i].fi,a[i].fi+=a[i-1].fi,a[i].se=i; sort(a,a+n+1); for(int i=0;i<=n;i++) { if(i<n&&a[i].fi==a[i+1].fi) nxt[a[i].se+1]=a[i+1].se; else nxt[a[i].se+1]=n+1; } 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][0]=n+1; } else { u++; p[i][0]=mn[u]; } } p[n+1][0]=n+1; for(int j=1;j<=7;j++) { for(int i=1;i<=n+1;i++) { ll x=i; for(int k=0;k<6;k++) { x=p[x][j-1]; } p[i][j]=x; } } pw[0]=1; for(int i=1;i<=9;i++) pw[i]=pw[i-1]*6; ll q; cin >> q; for(int i=1;i<=q;i++) { ll l,r,ans=0; cin >> l >> r; l=mn[l]; if(nxt[l]>r) {cout << 0 << '\n';continue;} else ans++; //cout << nxt[l] << '\n'; for(int j=7;j>=0;j--) { for(int k=0;k<5;k++) { if(nxt[p[l][j]]<=r) { l=p[l][j]; ans+=pw[j]; } else break; } } 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...