Submission #338577

#	Time	Username	Problem	Language	Result	Execution time	Memory
338577		Drew_	Secret (JOI14_secret)	C++14	100 / 100	529 ms	8428 KiB

secret

#include "secret.h"


int const MAX = 1e3 + 7;

int len;
int data[MAX][MAX];

void rc(int l, int r, int A[])
{
	if (l == r)
	{
		data[l][l] = A[l];
		return;
	}

	int mid = (l + r) / 2;
	rc(l, mid, A);
	rc(mid+1, r, A);

	for (int i = mid-1; i >= l; --i)
		data[i][mid] = Secret(A[i], data[i+1][mid]);
	for (int i = mid+2; i <= r; ++i)
		data[mid+1][i] = Secret(data[mid+1][i-1], A[i]);
	return;
}

void Init(int N, int A[]) {
	len = N;
	rc(0, N-1, A);
}

int query_rc(int l, int r, int p, int q)
{
	if (l == r)
		return data[l][l];

	int mid = (l + r) / 2;
	if (mid == q)
		return data[p][mid];
	if (mid+1 == p)
		return data[mid+1][q];

	if (p <= mid && mid+1 <= q)
		return Secret(data[p][mid], data[mid+1][q]);

	if (q < mid)
		return query_rc(l, mid, p, q);
	return query_rc(mid+1, r, p, q);
}

int Query(int L, int R) {
	return query_rc(0, len-1, L, R);
}

• Subtask 1: 100 / 100