#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7;
const ll maxn = 2e5 + 5;
const ll INF = 1e9;
const ll INFL = 1e18;
ll n,m,k=0;
ll a[maxn];
const ll lg = 25;
ll up[maxn][lg];
#define d(x) cout<<"DEBUG: "<<(#x)<<" = "<<x<<'\n'
void _(){
cin>>n;
for(ll i=1;i<=n;i++) cin>>a[i];
ll cm = accumulate(a+1, a+n+1, 0ll);
map<ll, ll>bf;
ll tmp = n+1;
for(ll i=n;i>=0;i--){
if(bf.count(cm)) tmp = min(tmp, bf[cm]);
bf[cm] = i;
up[i][0] = tmp;
cm -= a[i];
}
up[n+1][0] = n+1;
for(ll i=1;i<lg;i++){
for(ll j=0;j<=n+1;j++){
up[j][i] = up[up[j][i-1]][i-1];
}
}
cin>>m;
for(ll t=1;t<=m;t++){
ll l, r;
cin>>l>>r;
ll cv = 0;
l --;
for(ll i=lg-1;i>=0;i--){
if(up[l][i] == 0) continue;
if(up[l][i] <= r){
cv += 1ll<<i;
l = up[l][i];
}
}
cout<<cv<<'\n';
}
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
ll t=1;
// cin>>t;
while(t--){
_();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |