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<iostream>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<math.h>
#include<vector>
#include<stdio.h>
#include<utility>
#include<iomanip>
#include<string.h>
#include<limits.h>
#include<algorithm>
#include<functional>
#include<unordered_map>
using namespace std;
#pragma GCC target("popcnt")
#define MOD 1000000007
// #define int long long
#define ss second
#define ff first
#define endl '\n'
void solve(){
int n; cin>>n;
vector<int> a(n+1);
for(int i=1; i<=n; i++) cin>>a[i];
vector<vector<int> > p(n+3,vector<int>(11));
int sum=0;
map<int,int> mp;
mp[0]=n+1;
p[n+1][0]=n+2;
p[n+2][0]=n+2;
for(int i=n; i>=1; i--){
sum+=a[i];
if(i==n){
if(mp[sum]==0) p[i][0]=n+2;
else p[i][0]=mp[sum];
}else{
if(mp[sum]==0) p[i][0]=p[i+1][0];
else p[i][0]=min(mp[sum],p[i+1][0]);
}
mp[sum]=i;
}
for(int i=1; i<=10; i++){
for(int j=1; j<=n+2; j++){
p[j][i]=j;
for(int k=1; k<=4; k++){
p[j][i]=p[p[j][i]][i-1];
}
}
}
vector<int> dp(11);
dp[0]=1;
for(int i=1; i<=10; i++) dp[i]=dp[i-1]*4;
int q; cin>>q;
while(q--){
int l,r; cin>>l>>r;
int ans=0;
for(int i=10; i>=0; i--){
while(p[l][i]-1<=r){
l=p[l][i];
ans+=dp[i];
}
}
cout<<ans<<endl;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
// cin>>T;
while(T--){
solve();
cout<<endl;
}
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... |