Submission #365141

#	Time	Username	Problem	Language	Result	Execution time	Memory
365141		Bill_00	Secret (JOI14_secret)	C++14	0 / 100	548 ms	8496 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
int a[1001],n;
int ans[1001][1001];
void build(int l,int r,int height){
	if(l>r){
		return;
	}
	if(l==r){
		ans[l][r]=a[l];
		return;
	}
	if(height==8){
		int m=l+r>>1;
		ans[m][m]=a[m];
		ans[m+1][m+1]=a[m+1];
		if(m-l==3){
			ans[l][l+1]=Secret(a[l],a[l+1]);
			ans[l+2][l+3]=Secret(a[l+2],a[l+3]);
			ans[l][l+3]=Secret(ans[l][l+1],ans[l+2][l+3]);
			ans[l+1][l+3]=Secret(a[l+1],ans[l+2][l+3]);
		}
		else{
			int k=a[m];
			for(int i=m-1;i>=l;i--){
				k=Secret(a[i],k);
				ans[i][m]=k;
			}
		}
		if(r-m-1==3){
			ans[r-1][r]=Secret(a[r-1],a[r]);
			ans[r-3][r-2]=Secret(a[r-3],a[r-2]);
			ans[r-3][r]=Secret(ans[r-1][r],ans[r-3][r-2]);
			ans[r-3][r-1]=Secret(ans[r-3][r-2],a[r-1]);
		}
		else{
			int k=a[m+1];
			for(int i=m+2;i<=r;i++){
				k=Secret(k,a[i]);
				ans[m+1][i]=k;
			}
		}
		return;
	}
	int m=l+r>>1;
	int k=a[m];
	ans[m][m]=a[m];
	for(int i=m-1;i>=l;i--){
		k=Secret(a[i],k);
		ans[i][m]=k;
	}
	k=a[m+1];
	ans[m+1][m+1]=a[m+1];
	for(int i=m+2;i<=r;i++){
		k=Secret(k,a[i]);
		ans[m+1][i]=k;
	}
	build(l,m-1,height+1);
	build(m+2,r,height+1);
}
int query(int l,int r,int height,int L,int R){
	int m=l+r>>1;
	if(L<=m && m<=R){
		if(m==R){
			return ans[L][m];
		}
		else return Secret(ans[L][m],ans[m+1][R]);
	}
	if(L<=(m+1) && (m+1)<=R){
		if(m+1==L){
			return ans[m+1][R];
		}
		else return Secret(ans[L][m],ans[m+1][R]);
	}
	if(height==8){
		if(m>R){
			if(R-L==2){
				return Secret(ans[L][L+1],a[L+2]);
			}
			else{
				return Secret(a[L],a[R]);
			}
		}
		if(L>m+1){
			if(R-L==2){
				return Secret(a[R-2],ans[R-1][R]);
			}
			else return Secret(a[L],a[R]);
		}
	}
	if(m>R){
		return query(l,m-1,height+1,L,R);
	}
	else return query(m+1,r,height+1,L,R);
}
void Init(int N, int A[]){
	n=N;
	for(int i=0;i<n;i++) a[i]=A[i];
	build(0,n-1,1);
}

int Query(int L, int R) {
	if(L==R) return a[L];
	return query(0,n-1,1,L,R);
}

Compilation message (stderr)

secret.cpp: In function 'void build(int, int, int)':
secret.cpp:15:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |   int m=l+r>>1;
      |         ~^~
secret.cpp:46:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int m=l+r>>1;
      |        ~^~
secret.cpp: In function 'int query(int, int, int, int, int)':
secret.cpp:63:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |  int m=l+r>>1;
      |        ~^~

• Subtask 1: 0 / 100