제출 #1254816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254816		ssitaram	비밀 (JOI14_secret)	C++20	100 / 100	341 ms	4432 KiB

secret

#include "secret.h"

int N;
int seg[1000][10], mask[1000];
int A[1000];

void div(int lev, int l, int r) {
	if (l == r) return;
	int m = (l + r) / 2;
	for (int i = l; i <= m; ++i) mask[i] ^= 1 << lev;
	seg[m][lev] = A[m];
	for (int i = m - 1; i >= l; --i) seg[i][lev] = Secret(A[i], seg[i + 1][lev]);
	seg[m + 1][lev] = A[m + 1];
	for (int i = m + 2; i <= r; ++i) seg[i][lev] = Secret(seg[i - 1][lev], A[i]);
	div(lev + 1, l, m);
	div(lev + 1, m + 1, r);
}

void Init(int Nn, int Ar[]) {
	N = Nn;
	for (int i = 0; i < N; ++i) {
		A[i] = Ar[i];
	}
	div(0, 0, N - 1);
}

int Query(int L, int R) {
	if (L == R) return A[L];
	int lev = __builtin_ctz(mask[L] ^ mask[R]);
	return Secret(seg[L][lev], seg[R][lev]);
}

• Subtask 1: 100 / 100