Submission #548868

#	Time	Username	Problem	Language	Result	Execution time	Memory
548868		rainboy	Secret (JOI14_secret)	C11	100 / 100	499 ms	4424 KiB

secret

#include "secret.h"

#define N	1000
#define M	10000

int bb[M], *ptr, *cc[N], n;

void solve(int *aa, int l, int r) {
	int m, i;

	if (l > r)
		return;
	m = (l + r) / 2;
	cc[m] = ptr, ptr += r - l + 1;
	cc[m][m - l] = aa[m];
	for (i = m - 1; i >= l; i--)
		cc[m][i - l] = Secret(aa[i], cc[m][i + 1 - l]);
	if (l < r) {
		cc[m][m + 1 - l] = aa[m + 1];
		for (i = m + 2; i <= r; i++)
			cc[m][i - l] = Secret(cc[m][i - 1 - l], aa[i]);
	}
	solve(aa, l, m - 1), solve(aa, m + 2, r);
}

void Init(int n_, int *aa) {
	n = n_, ptr = bb, solve(aa, 0, n - 1);
}

int query(int l, int r, int ql, int qr) {
	int m = (l + r) / 2;

	if (qr == m)
		return cc[m][ql - l];
	if (ql == m + 1)
		return cc[m][qr - l];
	if (ql <= m && m + 1 <= qr)
		return Secret(cc[m][ql - l], cc[m][qr - l]);
	return qr < m ? query(l, m - 1, ql, qr) : query(m + 2, r, ql, qr);
}

int Query(int l, int r) {
	return query(0, n - 1, l, r);
}

• Subtask 1: 100 / 100