Submission #1196497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196497		Hydrolyzed	Secret (JOI14_secret)	C++20	0 / 100	341 ms	4376 KiB

secret

#include "secret.h"

const int MxN = 1010;
const int MxL = 22;

int a[MxN], mem[MxL][MxN], state[MxN];

void solve(int l, int r, int lvl) {
	if(l >= r) {
		return ;
	}
	int mid = (l + r) >> 1;
	mem[lvl][mid] = a[mid];
	for(int i=mid-1; i>=l; --i) {
		mem[lvl][i] = Secret(a[i], mem[lvl][i + 1]);
	}
	mem[lvl][mid + 1] = a[mid + 1];
	for(int i=mid+2; i<=r; ++i) {
		mem[lvl][i] = Secret(a[i], mem[lvl][i - 1]);
	}
	for(int i=mid+1; i<=r; ++i) {
		state[i] ^= (1 << lvl);
	}
	solve(l, mid, lvl + 1);
	solve(mid + 1, r, lvl + 1);
}

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

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

• Subtask 1: 0 / 100