oj.uz

답안 #956548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956548 2024-04-02T06:59:26 Z Batorgil952 Sum Zero (RMI20_sumzero) C++14
22 / 100
 81 ms 23892 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair

using namespace std;

const ll N=4e5+5;
ll a[N];
ll dp[N][19];
map< ll, ll > M;

int main(){
	ll n, i, j, q, l, r, s, ans;
	
	scanf("%lld",&n);
	
	for(i=1; i<=n; i++){
		scanf("%lld",&a[i]);
	}
	
	s=0;
	M[0]=0;
	for(i=1; i<=n; i++){
		s+=a[i];
		if(M[s]!=0){
			dp[i][1]=M[s]+1;
		}
		else{
			if(s==0) dp[i][1]=1;
			else dp[i][1]=-1;
		}
		if(dp[i][1]==-1 && i>1){
			dp[i][1]=dp[i-1][1];
		}
		else if(i>1) dp[i][1]=max(dp[i][1], dp[i-1][1]);
		M[s]=i;
	}
	
	for(i=1; i<=n; i++){
//		cout<<dp[i][1]<<" ";
		for(j=2; 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;
// 			cout<<dp[i][j]<<" ";
		}
// 		cout<<endl;
	}
	
	scanf("%lld",&q);
	
	while(q--){
		scanf("%lld",&l);
		scanf("%lld",&r);
		ans=0;
		for(i=18; i>=1; i--){
			if(r>=0){
				if(dp[r][i]>=l){
					ans+=(1<<(i-1));
					r=dp[r][i];
					r--;
				}
			}
		}
		printf("%lld\n", ans);
	}
	
	return 0;
}

Compilation message

sumzero.cpp: In function 'int main()':
sumzero.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%lld",&n);
      |  ~~~~~^~~~~~~~~~~
sumzero.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   scanf("%lld",&a[i]);
      |   ~~~~~^~~~~~~~~~~~~~
sumzero.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%lld",&q);
      |  ~~~~~^~~~~~~~~~~
sumzero.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%lld",&l);
      |   ~~~~~^~~~~~~~~~~
sumzero.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%lld",&r);
      |   ~~~~~^~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 3 ms 4700 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct
4 Correct 4 ms 4700 KB Output is correct
5 Correct 3 ms 4792 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct
7 Runtime error 81 ms 23892 KB Memory limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 3 ms 4700 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct
4 Correct 4 ms 4700 KB Output is correct
5 Correct 3 ms 4792 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct
7 Runtime error 81 ms 23892 KB Memory limit exceeded
8 Halted 0 ms 0 KB -