#include <bits/stdc++.h>
#define ll long long
#define INF 10000000
using namespace std;
#define LOG 7
#define MAX 400002
int main(){
int n, q, l, r, la;
ll pr = 0, a;
cin>>n;
int up[n + 2][LOG];
la = n + 1;
map<ll, int> ma;
ma[0] = 0;
for (int i = 1; i <= n; i++){
cin>>a;
pr += a;
if (ma.find(pr) != ma.end()){
if (la == n + 1) la = ma[pr];
la = max(la, ma[pr]);
}
up[i][0] = la;
ma[pr] = i;
}
ma.clear();
for (int i = 0; i < LOG; i++) up[0][i] = n + 1, up[n + 1][i] = n + 1;
for (int i = 1; i < LOG; i++){
for (int j = 1; j <= n; j++){
up[j][i] = j;
for (int k = 0; k < 8; k++){
up[j][i] = up[up[j][i]][i - 1];
}
}
}
cin>>q;
while (q--){
cin>>l>>r;
int st = r, ans = 0;
l--;
for (int i = 19; i >= 0; i--){
int jmp = r;
int rep = (1<<(i % 3));
for (int j = 0; j < rep; j++) jmp = up[jmp][i/3];
if (jmp >= l && jmp != n + 1){
r = jmp;
ans += (1<<i);
}
}
cout<<ans<<"\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |