# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
const int N = 4e5 + 2, inf = 1e9;
int t, n, a,par[N][5],nxt[N],frst[N],v[N];
long long pr;
map <long long, int> mp;
main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
mp[pr] = 0;
for (int i = 1; i <= n; i++) {
nxt[i] = -1;
cin>>a; pr += a;
if (mp[pr] != 0 || pr == 0) { nxt[mp[pr] + 1] = i; }
mp[pr] = i;
}
int mn = inf, m = 0;
for (int i = n; i >= 1; i--) {
if (nxt[i] == -1) continue;
if (mn <= nxt[i]) continue;
v[m++] = i; mn = nxt[i];
}
sort(v, v + m); // if (l[i] > l[j]) ---> r[i] > r[j]
for (int i = 1; i < N; i++) frst[i] = n + 1;
for (int i = m - 1; i >= 0;i--){
frst[v[i]] = i + 1;
}
frst[n + 1] = n + 1;
for (int i = n; i >= 1; i--) {
frst[i] = min(frst[i], frst[i + 1]);
}
for (int i = m - 1; i >= 0; i--) {
par[i + 1][0] = frst[nxt[v[i]] + 1];
}
for (int j = 1; j <= 4; j++) {
for (int i = 1; i <= m; i++) {
int cur = i;
for (int it = 1; it <= 8; it++) {
if (par[cur][j - 1] == n + 1 || cur == n + 1) {
cur = n + 1; break;
}
cur = par[par[cur][j - 1]][j - 1];
}
par[i][j] = cur;
}
}
int q,le,ri,st_idx,cur,ans;
cin>>q;
while (q--) {
cin>>le>>ri;
st_idx = frst[le];
if (st_idx == n + 1 || v[st_idx - 1] > ri) {
cout<<0<<"\n"; continue;
}
cur = st_idx; ans = 0;
for (int i = 4; i >= 0; i--) {
while(par[cur][i] != n + 1 && v[par[cur][i] - 1] <= ri) {
cur = par[cur][i];
ans += (1<<(4*i));
}
}
if (nxt[v[cur - 1]] <= ri) ans++;
cout<<ans<<"\n";
}
}
Compilation message
sumzero.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
10 | main() {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2132 KB |
Output is correct |
2 |
Correct |
4 ms |
2132 KB |
Output is correct |
3 |
Correct |
4 ms |
2132 KB |
Output is correct |
4 |
Correct |
4 ms |
2132 KB |
Output is correct |
5 |
Correct |
3 ms |
2132 KB |
Output is correct |
6 |
Correct |
5 ms |
2132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2132 KB |
Output is correct |
2 |
Correct |
4 ms |
2132 KB |
Output is correct |
3 |
Correct |
4 ms |
2132 KB |
Output is correct |
4 |
Correct |
4 ms |
2132 KB |
Output is correct |
5 |
Correct |
3 ms |
2132 KB |
Output is correct |
6 |
Correct |
5 ms |
2132 KB |
Output is correct |
7 |
Correct |
88 ms |
7252 KB |
Output is correct |
8 |
Correct |
90 ms |
8548 KB |
Output is correct |
9 |
Correct |
81 ms |
5240 KB |
Output is correct |
10 |
Correct |
79 ms |
7176 KB |
Output is correct |
11 |
Correct |
86 ms |
7756 KB |
Output is correct |
12 |
Correct |
104 ms |
5276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2132 KB |
Output is correct |
2 |
Correct |
4 ms |
2132 KB |
Output is correct |
3 |
Correct |
4 ms |
2132 KB |
Output is correct |
4 |
Correct |
4 ms |
2132 KB |
Output is correct |
5 |
Correct |
3 ms |
2132 KB |
Output is correct |
6 |
Correct |
5 ms |
2132 KB |
Output is correct |
7 |
Correct |
88 ms |
7252 KB |
Output is correct |
8 |
Correct |
90 ms |
8548 KB |
Output is correct |
9 |
Correct |
81 ms |
5240 KB |
Output is correct |
10 |
Correct |
79 ms |
7176 KB |
Output is correct |
11 |
Correct |
86 ms |
7756 KB |
Output is correct |
12 |
Correct |
104 ms |
5276 KB |
Output is correct |
13 |
Runtime error |
412 ms |
23608 KB |
Memory limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |