#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5+5;
const int step = 74;
int n;
pair<long long, int> A[maxn];
int mx[maxn], mx_b[maxn], mx_b2[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
memset(mx, -1, sizeof(mx));
for(int i = 1; i <= n; i++){
cin >> A[i].first;
A[i].first += A[i-1].first;
A[i].second = i;
}
sort(A, A+n+1);
for(int i = 1; i <= n; i++){
if(A[i].first == A[i-1].first)mx[A[i].second] = A[i-1].second;
}
for(int i = 0; i <= n; i++){
if(i)mx[i] = max(mx[i], mx[i-1]);
mx_b[i] = i;
for(int j = 0; j < step; j++){
if(mx_b[i] == -1)break;
mx_b[i] = mx[mx_b[i]];
}
mx_b2[i] = i;
for(int j = 0; j < step; j++){
if(mx_b2[i] == -1)break;
mx_b2[i] = mx_b[mx_b2[i]];
}
}
int q;
cin >> q;
while(q--){
int l, r, ans = 0;
cin >> l >> r;
while(mx[r] >= l-1){
if(mx_b2[r] >= l-1){
r = mx_b2[r];
ans += step*step;
}
if(mx_b[r] >= l-1){
r = mx_b[r];
ans += step;
}
if(mx[r] >= l-1){
r = mx[r];
ans++;
}
}
cout << ans << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6492 KB |
Output is correct |
2 |
Correct |
3 ms |
6492 KB |
Output is correct |
3 |
Correct |
3 ms |
6492 KB |
Output is correct |
4 |
Correct |
3 ms |
6492 KB |
Output is correct |
5 |
Correct |
3 ms |
6492 KB |
Output is correct |
6 |
Correct |
5 ms |
6492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6492 KB |
Output is correct |
2 |
Correct |
3 ms |
6492 KB |
Output is correct |
3 |
Correct |
3 ms |
6492 KB |
Output is correct |
4 |
Correct |
3 ms |
6492 KB |
Output is correct |
5 |
Correct |
3 ms |
6492 KB |
Output is correct |
6 |
Correct |
5 ms |
6492 KB |
Output is correct |
7 |
Correct |
126 ms |
7160 KB |
Output is correct |
8 |
Correct |
66 ms |
6972 KB |
Output is correct |
9 |
Correct |
129 ms |
7248 KB |
Output is correct |
10 |
Correct |
106 ms |
6996 KB |
Output is correct |
11 |
Correct |
63 ms |
7052 KB |
Output is correct |
12 |
Correct |
121 ms |
7056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6492 KB |
Output is correct |
2 |
Correct |
3 ms |
6492 KB |
Output is correct |
3 |
Correct |
3 ms |
6492 KB |
Output is correct |
4 |
Correct |
3 ms |
6492 KB |
Output is correct |
5 |
Correct |
3 ms |
6492 KB |
Output is correct |
6 |
Correct |
5 ms |
6492 KB |
Output is correct |
7 |
Correct |
126 ms |
7160 KB |
Output is correct |
8 |
Correct |
66 ms |
6972 KB |
Output is correct |
9 |
Correct |
129 ms |
7248 KB |
Output is correct |
10 |
Correct |
106 ms |
6996 KB |
Output is correct |
11 |
Correct |
63 ms |
7052 KB |
Output is correct |
12 |
Correct |
121 ms |
7056 KB |
Output is correct |
13 |
Correct |
586 ms |
13272 KB |
Output is correct |
14 |
Correct |
356 ms |
19428 KB |
Output is correct |
15 |
Correct |
694 ms |
19308 KB |
Output is correct |
16 |
Correct |
579 ms |
18308 KB |
Output is correct |
17 |
Correct |
371 ms |
19028 KB |
Output is correct |
18 |
Correct |
668 ms |
19328 KB |
Output is correct |