# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
516995 | 2022-01-22T10:44:29 Z | Stickfish | Sum Zero (RMI20_sumzero) | C++17 | 322 ms | 23220 KB |
#include <iostream> #include <map> #include <vector> using namespace std; using ll = long long; const int MAXN = 500000; int a[MAXN]; vector<int> redg[MAXN]; signed main() { int n; cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; map<ll, int> mp; mp[0] = -1; ll psm = 0; for (int i = 0; i < n; ++i) { psm += a[i]; if (mp.find(psm) == mp.end()) { a[i] = -2; } else { a[i] = mp[psm]; } if (i && a[i - 1] > a[i]) a[i] = a[i - 1]; if (a[i] >= -1) { redg[i].push_back(a[i]); for (int j = 1;; ++j) { int v = redg[i][j - 1]; if (v == -1 || j - 1 >= redg[v].size()) break; redg[i].push_back(redg[v][j - 1]); } } mp[psm] = i; } int q; cin >> q; while (q--) { int l, r; cin >> l >> r; --l; int v = r - 1; int ans = 0; int j = 20; while (true) { if (v < l || j == -1) break; if (j >= redg[v].size() || redg[v][j] + 1 < l) { --j; } else { ans += (1 << j); v = redg[v][j]; } } cout << ans << endl; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 12492 KB | Output is correct |
2 | Correct | 21 ms | 12448 KB | Output is correct |
3 | Correct | 19 ms | 12584 KB | Output is correct |
4 | Correct | 20 ms | 12552 KB | Output is correct |
5 | Correct | 18 ms | 12428 KB | Output is correct |
6 | Correct | 19 ms | 12552 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 12492 KB | Output is correct |
2 | Correct | 21 ms | 12448 KB | Output is correct |
3 | Correct | 19 ms | 12584 KB | Output is correct |
4 | Correct | 20 ms | 12552 KB | Output is correct |
5 | Correct | 18 ms | 12428 KB | Output is correct |
6 | Correct | 19 ms | 12552 KB | Output is correct |
7 | Runtime error | 322 ms | 23220 KB | Memory limit exceeded |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 12492 KB | Output is correct |
2 | Correct | 21 ms | 12448 KB | Output is correct |
3 | Correct | 19 ms | 12584 KB | Output is correct |
4 | Correct | 20 ms | 12552 KB | Output is correct |
5 | Correct | 18 ms | 12428 KB | Output is correct |
6 | Correct | 19 ms | 12552 KB | Output is correct |
7 | Runtime error | 322 ms | 23220 KB | Memory limit exceeded |
8 | Halted | 0 ms | 0 KB | - |