#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;
vector<pair<ll, int>> ve(n + 1);
ve[0].first = 0, ve[1].second = 0;
for (int i = 1; i <= n; i++){
up[i][0] = n + 1;
cin>>a;
pr += a;
ve[i].first = pr, ve[i].second = i;
}
sort(ve.begin(), ve.end());
for (int i = 1; i <= n; i++){
if (ve[i].first == ve[i - 1].first){
up[ve[i].second][0] = ve[i - 1].second;
}
}
for (int i = 0; i < LOG; i++) up[0][i] = n + 1, up[n + 1][i] = n + 1;
for (int i = 1; i <= n; i++){
if (up[i - 1][0] == n + 1) continue;
if (up[i][0] == n + 1) up[i][0] = up[i - 1][0];
else up[i][0] = max(up[i][0], up[i - 1][0]);
}
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... |