제출 #930308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930308		noyancanturk	Secret (JOI14_secret)	C++17	100 / 100	369 ms	4528 KiB

secret

#include "secret.h"
#include <cassert>
const int lim=1100;

int n,*a;
int aa[15][lim];

void dnc(int l,int r,int dep=0){
	if(l==r){
		return;
	}
	int mid=(l+r)>>1;
	aa[dep][mid]=a[mid];
	for(int i=mid-1;l<=i;i--){
		aa[dep][i]=Secret(a[i],aa[dep][i+1]);
	}
	aa[dep][mid+1]=a[mid+1];
	for(int i=mid+2;i<=r;i++){
		aa[dep][i]=Secret(aa[dep][i-1],a[i]);
	}
	dnc(l,mid,dep+1),dnc(mid+1,r,dep+1);
}

void Init(int N, int A[]) {
	n=N;
	a=A;
	dnc(0,n-1);
}

int Query(int L, int R) {
	if(L==R){
		return a[L];
	}
	int l=0,r=n-1,dep=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(L<=mid&&mid<R){
			return Secret(aa[dep][L],aa[dep][R]);
		}else if(mid+1==L){
			return aa[dep][R];
		}
		else if(mid==R){
			return aa[dep][L];
		}else if(mid<L){
			l=mid+1;
		}else{
			r=mid;
		}
		dep++;
	}
	return -1;
}

• Subtask 1: 100 / 100