Submission #1091665

#TimeUsernameProblemLanguageResultExecution timeMemory
1091665giorgi123glmSum Zero (RMI20_sumzero)C++17
22 / 100
91 ms25068 KiB
#include <iostream> #include <vector> #include <map> using namespace std; struct defaultval { long long i = -1; operator long long() const { return i; } defaultval (long long i) : i (i) {} defaultval () : i (-1) {} }; int main () { ios::sync_with_stdio (false); cin.tie (0); cout.tie (0); long long n = 0; cin >> n; vector <long long> v (n + 1); for (long long i = 1; i <= n; i++) cin >> v[i]; long long pref = 0; map <long long, defaultval> prefmap; vector <vector <long long> > binlift (n + 1, vector <long long> (20, 1e9)); prefmap[0] = 0; for (long long i = 1; i <= n; i++) { pref += v[i]; if (prefmap[pref] == -1) prefmap[pref] = i; else { if (binlift[prefmap[pref] + 1][0] == 1e9) binlift[prefmap[pref] + 1][0] = i; prefmap[pref] = i; } } for (long long i = n - 1; i >= 1; i--) { binlift[i][0] = min (binlift[i][0], binlift[i + 1][0]); for (long long j = 1; j <= 19; j++) if (binlift[i][j - 1] + 1 > n) break; else binlift[i][j] = binlift[binlift[i][j - 1] + 1][j - 1]; } long long q = 0; cin >> q; while (q--) { long long l = 0, r = 0; cin >> l >> r; long long ans = 0; for (long long p = 19; p >= 0; p--) if (l <= n && binlift[l][p] <= r) ans += (1 << p), l = binlift[l][p] + 1; cout << ans << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...