# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
517005 | 2022-01-22T11:03:41 Z | Stickfish | Sum Zero (RMI20_sumzero) | C++17 | 982 ms | 45152 KB |
#include <iostream> #include <map> #include <vector> using namespace std; using ll = long long; #define endl '\n' const int MAXN = 400000; int a[MAXN]; vector<int> redg[MAXN]; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); 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 = i; for (int t = 0; t < 4; ++t) { //cout << i << ' ' << j << ' ' << v << endl; if (v == -1 || j - 1 >= redg[v].size()) { v = -2; break; } else { v = redg[v][j - 1]; } } if (v != -2) redg[i].push_back(v); else break; } } mp[psm] = i; } //return 0; mp.clear(); int q; cin >> q; while (q--) { int l, r; cin >> l >> r; --l; int v = r - 1; int ans = 0; int j = 10; while (true) { if (v < l || j == -1) break; if (j >= redg[v].size() || redg[v][j] + 1 < l) { --j; } else { ans += (1 << j) << j; v = redg[v][j]; } } cout << ans << endl; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 10188 KB | Output is correct |
2 | Correct | 8 ms | 10052 KB | Output is correct |
3 | Correct | 11 ms | 10060 KB | Output is correct |
4 | Correct | 8 ms | 9992 KB | Output is correct |
5 | Correct | 8 ms | 10036 KB | Output is correct |
6 | Correct | 9 ms | 10060 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 10188 KB | Output is correct |
2 | Correct | 8 ms | 10052 KB | Output is correct |
3 | Correct | 11 ms | 10060 KB | Output is correct |
4 | Correct | 8 ms | 9992 KB | Output is correct |
5 | Correct | 8 ms | 10036 KB | Output is correct |
6 | Correct | 9 ms | 10060 KB | Output is correct |
7 | Correct | 125 ms | 17748 KB | Output is correct |
8 | Correct | 127 ms | 18172 KB | Output is correct |
9 | Correct | 125 ms | 15984 KB | Output is correct |
10 | Correct | 125 ms | 17668 KB | Output is correct |
11 | Correct | 108 ms | 17476 KB | Output is correct |
12 | Correct | 139 ms | 15820 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 10188 KB | Output is correct |
2 | Correct | 8 ms | 10052 KB | Output is correct |
3 | Correct | 11 ms | 10060 KB | Output is correct |
4 | Correct | 8 ms | 9992 KB | Output is correct |
5 | Correct | 8 ms | 10036 KB | Output is correct |
6 | Correct | 9 ms | 10060 KB | Output is correct |
7 | Correct | 125 ms | 17748 KB | Output is correct |
8 | Correct | 127 ms | 18172 KB | Output is correct |
9 | Correct | 125 ms | 15984 KB | Output is correct |
10 | Correct | 125 ms | 17668 KB | Output is correct |
11 | Correct | 108 ms | 17476 KB | Output is correct |
12 | Correct | 139 ms | 15820 KB | Output is correct |
13 | Runtime error | 982 ms | 45152 KB | Memory limit exceeded |
14 | Halted | 0 ms | 0 KB | - |