#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 4e5 + 5;
int n, q, nxt[N], ku[N][19];
map<ll, int> mp;
void build_rmq() {
for (int i = 1; i <= n; ++i) ku[i][0] = nxt[i];
for (int j = 1; j <= 18; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
if (ku[i][j - 1] == 0) {
ku[i][j] = 0;
continue;
}
ku[i][j] = ku[ku[i][j - 1] + 1][j - 1];
}
}
void build() {
cin >> n;
ll sum = 0, x;
mp[0] = 0;
for (int i = 1; i <= n; ++i) nxt[i] = -1;
for (int i = 1; i <= n; ++i) {
cin >> x;
sum += x;
if (mp.count(sum)) nxt[mp[sum] + 1] = i;
mp[sum] = i;
}
mp.clear();
int pre = -1;
for (int i = n; i >= 1; --i) {
if (nxt[i] != -1) pre = (pre == -1 ? nxt[i] : min(pre, nxt[i]));
else nxt[i] = 0;
nxt[i] = (pre != -1 ? pre : 0);
}
build_rmq();
}
int que(int l, int r) {
int ans = 0;
for (int i = 18; i >= 0; --i)
if (l + (1 << i) - 1 <= n && ku[l][i] != 0 && ku[l][i] <= r) {
// dbg(l, i, ku[l][i]);
ans += 1 << i;
l = ku[l][i] + 1;
}
return ans;
}
void ouput() {
cin >> q;
while (q--) {
static int l, r; cin >> l >> r;
cout << que(l, r) << '\n';
}
}
void solve() {
build();
ouput();
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int tc = 1; // cin >> tc;
for (; tc; --tc) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4916 KB |
Output is correct |
2 |
Correct |
3 ms |
4956 KB |
Output is correct |
3 |
Correct |
4 ms |
4956 KB |
Output is correct |
4 |
Correct |
3 ms |
4696 KB |
Output is correct |
5 |
Correct |
3 ms |
4828 KB |
Output is correct |
6 |
Correct |
4 ms |
4956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4916 KB |
Output is correct |
2 |
Correct |
3 ms |
4956 KB |
Output is correct |
3 |
Correct |
4 ms |
4956 KB |
Output is correct |
4 |
Correct |
3 ms |
4696 KB |
Output is correct |
5 |
Correct |
3 ms |
4828 KB |
Output is correct |
6 |
Correct |
4 ms |
4956 KB |
Output is correct |
7 |
Correct |
58 ms |
15292 KB |
Output is correct |
8 |
Correct |
65 ms |
15816 KB |
Output is correct |
9 |
Correct |
63 ms |
13392 KB |
Output is correct |
10 |
Correct |
60 ms |
15184 KB |
Output is correct |
11 |
Correct |
54 ms |
15184 KB |
Output is correct |
12 |
Correct |
69 ms |
13396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4916 KB |
Output is correct |
2 |
Correct |
3 ms |
4956 KB |
Output is correct |
3 |
Correct |
4 ms |
4956 KB |
Output is correct |
4 |
Correct |
3 ms |
4696 KB |
Output is correct |
5 |
Correct |
3 ms |
4828 KB |
Output is correct |
6 |
Correct |
4 ms |
4956 KB |
Output is correct |
7 |
Correct |
58 ms |
15292 KB |
Output is correct |
8 |
Correct |
65 ms |
15816 KB |
Output is correct |
9 |
Correct |
63 ms |
13392 KB |
Output is correct |
10 |
Correct |
60 ms |
15184 KB |
Output is correct |
11 |
Correct |
54 ms |
15184 KB |
Output is correct |
12 |
Correct |
69 ms |
13396 KB |
Output is correct |
13 |
Runtime error |
378 ms |
50204 KB |
Memory limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |