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