Submission #239194

#	Time	Username	Problem	Language	Result	Execution time	Memory
239194		rqi	Secret (JOI14_secret)	C++14	100 / 100	526 ms	4472 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
int A[1005];
int val[1005][10];
int N;
void build(int L, int R, int lvl = 0){
	if(L > R) return;
	if(L == R){
		val[L][lvl] = A[L];
		return;
	}
	int M = (L+R)/2;
	val[M][lvl] = A[M];
	for(int i = M-1; i >= L; i--){
		val[i][lvl] = Secret(A[i], val[i+1][lvl]);
	}
	val[M+1][lvl] = A[M+1];
	for(int i = M+2; i <= R; i++){
		val[i][lvl] = Secret(val[i-1][lvl], A[i]);
	}
	build(L, M-1, lvl+1);
	build(M+2, R, lvl+1);
}

int query(int l, int r, int L = 0, int R = N-1, int lvl = 0){
	int M = (L+R)/2;
	if(r <= M-1){
		return query(l, r, L, M-1, lvl+1);
	}
	if(l >= M+2){
		return query(l, r, M+2, R, lvl+1);
	}
	
	if(l >= M+1){
		return val[r][lvl];
	}
	if(r <= M){
		return val[l][lvl];
	}

	return Secret(val[l][lvl], val[r][lvl]);
}




void Init(int _N, int a[]) {

	N = _N;
	for(int i = 0; i < N; i++) A[i] = a[i];
	build(0, N-1);
}

int Query(int L, int R) {
	return query(L, R);
}

• Subtask 1: 100 / 100