Submission #1262918

#TimeUsernameProblemLanguageResultExecution timeMemory
1262918trinhvtuanSum Zero (RMI20_sumzero)C++20
61 / 100
322 ms36708 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 (value, pos) including pos 0 vector<pair<ll,int>> vec; vec.reserve(n+1); ll cur = 0; vec.emplace_back(0LL, 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 (0 <= curpos && curpos <= n) lf[curpos] = prevpos; } } // accumulate so lf[i] = best available previous occurrence up to i for(int i=1;i<=n;i++) if (lf[i] < lf[i-1]) lf[i] = lf[i-1]; // free vec to reduce peak memory vec.clear(); vec.shrink_to_fit(); // compute LOG (number of layers for binary lifting) int LOG = 1; while((1<<LOG) <= n) ++LOG; // now 2^LOG > n // use 1D array to store st: st[k*(n+1) + i] int rows = LOG; int cols = n + 1; vector<int> st(rows * cols, -1); auto idx = [&](int k, int i){ return k * cols + i; }; // initialize level 0 for all positions 0..n for(int i=0;i<=n;i++){ st[idx(0,i)] = (i>=0 && i<=n) ? lf[i] : -1; // lf[0] is -1 normally } // build higher levels for(int k=1;k<rows;k++){ for(int i=0;i<=n;i++){ int mid = st[idx(k-1,i)]; st[idx(k,i)] = (mid == -1) ? -1 : st[idx(k-1, mid)]; } } int Q; cin >> Q; while(Q--){ int L,R; cin >> L >> R; int u = R; int ans = 0; for(int k=rows-1;k>=0;k--){ int to = st[idx(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...