# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
956694 | 2024-04-02T10:54:33 Z | Batorgil952 | Sum Zero (RMI20_sumzero) | C++14 | 278 ms | 28864 KB |
#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][12]; int b[N]; 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<=11; j++){ if((dp[dp[i][j-1]-1][j-1]-1)>0) dp[i][j]=dp[dp[dp[i][j-1]-1][j-1]-1][j-1]; else dp[i][j]=-1, j=20; } } b[0]=1; for(i=1; i<=11; i++){ b[i]=b[i-1]*3; } scanf("%d",&q); while(q--){ scanf("%d",&l); scanf("%d",&r); ans=0; for(i=11; i>=0; i--){ if(r>=l){ if(dp[r][i]>=l){ if(dp[dp[r][i]-1][i]>=l){ 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 2396 KB | Output is correct |
2 | Correct | 3 ms | 2648 KB | Output is correct |
3 | Correct | 3 ms | 2652 KB | Output is correct |
4 | Correct | 3 ms | 2396 KB | Output is correct |
5 | Correct | 2 ms | 2396 KB | Output is correct |
6 | Correct | 3 ms | 2504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 2396 KB | Output is correct |
2 | Correct | 3 ms | 2648 KB | Output is correct |
3 | Correct | 3 ms | 2652 KB | Output is correct |
4 | Correct | 3 ms | 2396 KB | Output is correct |
5 | Correct | 2 ms | 2396 KB | Output is correct |
6 | Correct | 3 ms | 2504 KB | Output is correct |
7 | Correct | 54 ms | 8540 KB | Output is correct |
8 | Correct | 61 ms | 9172 KB | Output is correct |
9 | Correct | 58 ms | 7508 KB | Output is correct |
10 | Correct | 54 ms | 8616 KB | Output is correct |
11 | Correct | 48 ms | 8368 KB | Output is correct |
12 | Correct | 57 ms | 7464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 2396 KB | Output is correct |
2 | Correct | 3 ms | 2648 KB | Output is correct |
3 | Correct | 3 ms | 2652 KB | Output is correct |
4 | Correct | 3 ms | 2396 KB | Output is correct |
5 | Correct | 2 ms | 2396 KB | Output is correct |
6 | Correct | 3 ms | 2504 KB | Output is correct |
7 | Correct | 54 ms | 8540 KB | Output is correct |
8 | Correct | 61 ms | 9172 KB | Output is correct |
9 | Correct | 58 ms | 7508 KB | Output is correct |
10 | Correct | 54 ms | 8616 KB | Output is correct |
11 | Correct | 48 ms | 8368 KB | Output is correct |
12 | Correct | 57 ms | 7464 KB | Output is correct |
13 | Runtime error | 278 ms | 28864 KB | Memory limit exceeded |
14 | Halted | 0 ms | 0 KB | - |