Submission #956707

#	Time	Username	Problem	Language	Result	Execution time	Memory
956707		Batorgil952	Sum Zero (RMI20_sumzero)	C++14	61 / 100	431 ms	22864 KiB

sumzero

#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][9];
int b[9];
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<=8; 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){
						if(dp[dp[dp[dp[i][j-1]-1][j-1]-1][j-1]-1][j-1]-1>0){
							dp[i][j]=dp[dp[dp[dp[dp[i][j-1]-1][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;
			}
			else dp[i][j]=-1, j=20;
		}
	}
	
	b[0]=1;
	for(i=1; i<=8; i++){
		b[i]=b[i-1]*5;
	}
	
	scanf("%d",&q);
	
	while(q--){
		scanf("%d",&l);
		scanf("%d",&r);
		ans=0;
		for(i=8; 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){
							if(dp[dp[dp[dp[r][i]-1][i]-1][i]-1][i]>=l){
								ans+=4*b[i];
								r=dp[dp[dp[dp[r][i]-1][i]-1][i]-1][i]-1;
								continue;
							}
							ans+=3*b[i];
							r=dp[dp[dp[r][i]-1][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)

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

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 0 / 39