#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |