Submission #415566

#	Time	Username	Problem	Language	Result	Execution time	Memory
415566		mbfibat	Secret (JOI14_secret)	C++17	100 / 100	571 ms	4348 KiB

secret

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

using namespace std;

int a[1001];
int val[1001][11], 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[mi][lev] = a[mi];
	for (int i = mi - 1; i >= l; i--)
		val[i][lev] = comb(a[i], val[i + 1][lev]);

	val[mi + 1][lev] = a[mi + 1];
	for (int i = mi + 2; i <= r; i++)
		val[i][lev] = comb(val[i - 1][lev], 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[L][lev], val[R][lev]);
	}
}

• Subtask 1: 100 / 100