Submission #1257035

#TimeUsernameProblemLanguageResultExecution timeMemory
1257035nguynSum Zero (RMI20_sumzero)C++20
0 / 100
2 ms576 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define F first #define S second #define pb push_back #define pii pair<int, int> const int N = 5e5 + 5; int nxt[N]; int depth[N]; int n, q; int a[N]; int p[N]; int jump[N]; map<int, int> mp; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; p[i] = p[i - 1] + a[i]; } cin >> q; nxt[n + 1] = n + 2; nxt[n + 2] = n + 2; for (int i = n; i >= 1; i--) { mp[p[i]] = i; if (mp.count(p[i - 1])) nxt[i] = min(nxt[i + 1], mp[p[i - 1]]) + 1; else nxt[i] = nxt[i + 1]; // cout << nxt[i][0] << ' '; } jump[n + 1] = jump[n + 2] = n + 2; depth[n + 1] = 0; for (int i = n; i >= 1; i--) { int p = nxt[i]; depth[i] = depth[p] + 1; if (depth[p] - depth[jump[p]] == depth[jump[p]] - depth[jump[jump[p]]]) jump[i] = jump[jump[p]]; else jump[i] = p; } while(q--) { int l, r; cin >> l >> r; assert(r <= n); int res = 0; while(nxt[l] <= r + 1) { if (jump[l] <= r + 1) res += depth[l] - depth[jump[l]], l = jump[l]; else res++, l = nxt[l]; } cout << res << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...