# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
956703 | Batorgil952 | Sum Zero (RMI20_sumzero) | C++14 | 3 ms | 2648 KiB |
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>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int N=4e5+5;
int dp[N][10];
int b[10];
unordered_map< ll, int > M;
int main(){
int n, i, j, q, l, r, ans, x;
ll s;
scanf("%d",&n);
s=0;
M[0]=0;
for(i=1; i<=n; i++){
scanf("%d",&x);
s+=x;
if(M[s]!=0){
dp[i][0]=M[s]+1;
}
else{
if(s==0) dp[i][0]=1;
else dp[i][0]=-1;
}
if(dp[i][0]==-1 && i>1){
dp[i][0]=dp[i-1][0];
}
else if(i>1) dp[i][0]=max(dp[i][0], dp[i-1][0]);
M[s]=i;
}
for(i=1; i<=n; i++){
for(j=1; j<=9; j++){
if(dp[i][j-1]-1>0){
if(dp[dp[i][j-1]-1][j-1]-1>0){
if(dp[dp[dp[i][j-1]-1][j-1]-1][j-1]-1>0){
dp[i][j]=dp[dp[dp[dp[i][j-1]-1][j-1]-1][j-1]-1][j-1];
}
else dp[i][j]=-1, j=20;
}
else dp[i][j]=-1, j=20;
}
else dp[i][j]=-1, j=20;
}
}
b[0]=1;
for(i=1; i<=9; i++){
b[i]=b[i-1]*4;
}
scanf("%d",&q);
while(q--){
scanf("%d",&l);
scanf("%d",&r);
ans=0;
for(i=9; i>=0; i--){
if(r>=l){
if(dp[r][i]>=l){
if(dp[dp[r][i]-1][i]>=l){
if(dp[dp[dp[r][i]-1][i]-1][i]>=l){
ans+=3*b[i];
r=dp[dp[r][i]-1][i]-1;
continue;
}
ans+=2*b[i];
r=dp[dp[r][i]-1][i]-1;
continue;
}
ans+=b[i];
r=dp[r][i]-1;
}
}
}
printf("%d\n", ans);
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |