Submission #1026119

#TimeUsernameProblemLanguageResultExecution timeMemory
1026119NValchanovSum Zero (RMI20_sumzero)C++17
0 / 100
3 ms10840 KiB
#include <bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; const int MAXN = 4e5 + 10; const int MAXQ = 4e5 + 10; const int MAXLOG = 22; int n, q; int a[MAXN]; int nxt[MAXN]; int lift[MAXN][MAXLOG]; pair < int, int > queries[MAXQ]; ll ans[MAXN]; map < ll, int > sums; void read() { cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; } cin >> q; for(int i = 1; i <= q; i++) { cin >> queries[i].first >> queries[i].second; } } void fill_nxt() { int minpos = MAXN - 1; ll cursum = 0; for(int i = n + 1; i >= 1; i--) { cursum += a[i]; if(sums.find(cursum) != sums.end()) minpos = min(minpos, sums[cursum]); sums[cursum] = i; nxt[i] = minpos; } } void solve() { for(int i = 1; i <= n + 1; i++) { lift[i][0] = nxt[i]; } lift[MAXN - 1][0] = MAXN - 1; for(int j = 1; j < MAXLOG; j++) { for(int i = 1; i <= n + 1; i++) { lift[i][j] = lift[lift[i][j - 1]][j - 1]; } lift[MAXN - 1][j] = lift[lift[MAXN - 1][j - 1]][j - 1]; } for(int j = MAXLOG - 1; j >= 0; j--) { for(int i = 1; i <= q; i++) { int left = queries[i].first; int right = queries[i].second; if(lift[left][j] <= right) { ans[i] += (1 << j); left = lift[left][j]; } queries[i].first = left; } } } void print() { for(int i = 1; i <= q; i++) { cout << ans[i] << endl; } cout << endl; } int main() { ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); read(); fill_nxt(); solve(); print(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...