This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#define ar array
const int N = 4e5 + 5;
int par[N][5];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
memset(par, -1, sizeof par);
unordered_map<long long, int> last;
long long pref = 0; last[pref] = n;
for(int i=n-1;~i;i--){
pref += a[i];
if(last.count(pref)) par[i][0] = last[pref];
last[pref] = i;
if(i + 1 < n && ~par[i+1][0]){
if(par[i][0] == -1) par[i][0] = par[i+1][0];
else par[i][0] = min(par[i][0], par[i+1][0]);
}
}
for(int j=1;j<5;j++){
for(int i=0;i<n;i++){
int x = i;
for(int l=0;l<16 && ~x;l++){
x = par[x][j-1];
} par[i][j] = x;
}
}
int q; cin>>q;
while(q--){
int l, r; cin>>l>>r;
l--;
int res = 0;
for(int j=4;~j;){
if(~par[l][j] && par[l][j] <= r){
l = par[l][j];
res += (1 << (j * 4));
} else j--;
}
cout<<res<<"\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |