oj.uz

답안 #956673

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956673 2024-04-02T10:02:04 Z Batorgil952 Sum Zero (RMI20_sumzero) C++14
61 / 100
 334 ms 38448 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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>=0){
				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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 4 ms 2796 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 4 ms 2648 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 4 ms 2796 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 4 ms 2648 KB Output is correct
7 Correct 60 ms 10716 KB Output is correct
8 Correct 63 ms 11560 KB Output is correct
9 Correct 56 ms 9764 KB Output is correct
10 Correct 56 ms 10820 KB Output is correct
11 Correct 49 ms 10668 KB Output is correct
12 Correct 58 ms 9700 KB Output is correct

Subtask #3
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 4 ms 2796 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 4 ms 2648 KB Output is correct
7 Correct 60 ms 10716 KB Output is correct
8 Correct 63 ms 11560 KB Output is correct
9 Correct 56 ms 9764 KB Output is correct
10 Correct 56 ms 10820 KB Output is correct
11 Correct 49 ms 10668 KB Output is correct
12 Correct 58 ms 9700 KB Output is correct
13 Runtime error 334 ms 38448 KB Memory limit exceeded
14 Halted 0 ms 0 KB -