oj.uz

Submission #956675

# Submission time Handle Problem Language Result Execution time Memory
956675 2024-04-02T10:07:23 Z Batorgil952 Sum Zero (RMI20_sumzero) C++14
61 / 100
 323 ms 38540 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,conserve-stack")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
#define ll long long
#define pb push_back
#define mp make_pair
 
using namespace std;
 
const int N=4e5+5;
int dp[N][19];
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<=18; j++){
			if((dp[i][j-1]-1)>0) dp[i][j]=dp[dp[i][j-1]-1][j-1];
			else dp[i][j]=-1, j=20;
		}
	}
	
	scanf("%d",&q);
	
	while(q--){
		scanf("%d",&l);
		scanf("%d",&r);
		ans=0;
		for(i=18; i>=0; i--){
			if(r>=l){
				if(dp[r][i]>=l){
					ans+=(1<<(i));
					r=dp[r][i];
					r--;
				}
			}
		}
		printf("%d\n", ans);
	}
	
	return 0;
}

Compilation message

sumzero.cpp: In function 'int main()':
sumzero.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
sumzero.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~
sumzero.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
sumzero.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%d",&l);
      |   ~~~~~^~~~~~~~~
sumzero.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d",&r);
      |   ~~~~~^~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 4 ms 2652 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 4 ms 2652 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 56 ms 10720 KB Output is correct
8 Correct 53 ms 11356 KB Output is correct
9 Correct 58 ms 9700 KB Output is correct
10 Correct 55 ms 10832 KB Output is correct
11 Correct 63 ms 10564 KB Output is correct
12 Correct 61 ms 9712 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 4 ms 2652 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 56 ms 10720 KB Output is correct
8 Correct 53 ms 11356 KB Output is correct
9 Correct 58 ms 9700 KB Output is correct
10 Correct 55 ms 10832 KB Output is correct
11 Correct 63 ms 10564 KB Output is correct
12 Correct 61 ms 9712 KB Output is correct
13 Runtime error 323 ms 38540 KB Memory limit exceeded
14 Halted 0 ms 0 KB -