Submission #1263244

#TimeUsernameProblemLanguageResultExecution timeMemory
1263244duonggsimpSum Zero (RMI20_sumzero)C++20
0 / 100
1098 ms41212 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; const int LOG = 20; int n, q; long long a[MAXN], pre[MAXN]; int nxt[MAXN][LOG + 1]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i]; pre[0] = 0; for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i]; map<long long, int> last; for (int i = n; i >= 0; i--) { if (last.count(pre[i])) nxt[i][0] = last[pre[i]]; else nxt[i][0] = n + 1; last[pre[i]] = i; } for (int j = 1; j <= LOG; j++) { for (int i = 0; i <= n + 1; i++) { int mid = nxt[i][j - 1]; if (mid <= n) nxt[i][j] = nxt[mid][j - 1]; else nxt[i][j] = n + 1; } } while (q--) { int l, r; cin >> l >> r; int ans = 0; int pos = l - 1; for (int j = LOG; j >= 0; j--) { if (nxt[pos][j] <= r) { ans += (1 << j); pos = nxt[pos][j]; } } cout << ans << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...