Submission #1262917

#TimeUsernameProblemLanguageResultExecution timeMemory
1262917trinhvtuanSum Zero (RMI20_sumzero)C++20
61 / 100
419 ms38340 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; if(!(cin >> n)) return 0; vector<ll> a(n+1); for(int i=1;i<=n;i++) cin >> a[i]; // build prefix sums and pairs (value, pos) vector<pair<ll,int>> vec; vec.reserve(n+1); ll cur = 0; vec.emplace_back(0LL, 0); // prefix sum at position 0 for(int i=1;i<=n;i++){ cur += a[i]; vec.emplace_back(cur, i); } sort(vec.begin(), vec.end(), [](const pair<ll,int>& A, const pair<ll,int>& B){ if (A.first != B.first) return A.first < B.first; return A.second < B.second; }); // lf[pos] = previous position with same prefix sum (or -1) vector<int> lf(n+1, -1); for(size_t i=1;i<vec.size();++i){ if (vec[i].first == vec[i-1].first){ int curpos = vec[i].second; int prevpos = vec[i-1].second; if (curpos >= 0 && curpos <= n) lf[curpos] = prevpos; } } // We don't need vec anymore -> free memory vec.clear(); vec.shrink_to_fit(); // accumulate so lf[i] is the best (rightmost) previous occurrence up to i for(int i=1;i<=n;i++){ if (lf[i] < lf[i-1]) lf[i] = lf[i-1]; } // binary lifting table int LOG = 1; while((1<<LOG) <= n) ++LOG; // st[k][i] = position after jumping 2^k steps from i (or -1) vector<vector<int>> st(LOG, vector<int>(n+1, -1)); for(int i=1;i<=n;i++) st[0][i] = lf[i]; for(int k=1;k<LOG;k++){ for(int i=1;i<=n;i++){ int mid = st[k-1][i]; st[k][i] = (mid == -1) ? -1 : st[k-1][mid]; } } int Q; cin >> Q; while(Q--){ int L,R; cin >> L >> R; int u = R; int ans = 0; for(int k=LOG-1;k>=0;k--){ int to = st[k][u]; if (to != -1 && to + 1 >= L){ ans += (1<<k); u = to; } } cout << ans << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...