Submission #416117

#	Time	Username	Problem	Language	Result	Execution time	Memory
416117		mbfibat	비밀 (JOI14_secret)	C++17	100 / 100	603 ms	4404 KiB

secret

#include "secret.h"
#include <iostream>

using namespace std;

int a[1001];
int val[11][1001], mask[1001];

int comb(int x, int y) {
	return Secret(x, y);
}

void init(int l, int r, int lev) {
	if (l == r) 
		return;

	int mi = (l + r) / 2;
	val[lev][mi] = a[mi];
	for (int i = mi - 1; i >= l; i--)
		val[lev][i] = comb(a[i], val[lev][i + 1]);

	val[lev][mi + 1] = a[mi + 1];
	for (int i = mi + 2; i <= r; i++)
		val[lev][i] = comb(val[lev][i - 1], a[i]);
	for (int i = mi + 1; i <= r; i++)
		mask[i] |= (1 << lev);
	init(l, mi, lev + 1);
	init(mi + 1, r, lev + 1);
}

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

int Query(int L, int R) {
	L++, R++;
	if (L == R) return a[L];
	else {
		int lev = __builtin_ctz(mask[L] ^ mask[R]);
		return Secret(val[lev][L], val[lev][R]);
	}
}

• Subtask 1: 100 / 100