Submission #156982

#	Time	Username	Problem	Language	Result	Execution time	Memory
156982		faremy	Secret (JOI14_secret)	C++14	100 / 100	593 ms	8440 KiB

secret

#include "secret.h"


const int MAXN = 1000;

int size = 0;
int precalc[MAXN][MAXN];


void dc(int left, int right)
{
	if (right - left <= 1)
		return;
	int middle = (left + right) / 2;

	for (int iElem = middle + 1; iElem < right; iElem++)
		precalc[middle][iElem] = Secret(precalc[middle][iElem - 1], precalc[iElem][iElem]);
	for (int iElem = middle - 2; iElem >= left; iElem--)
		precalc[iElem][middle - 1] = Secret(precalc[iElem][iElem], precalc[iElem + 1][middle - 1]);
	dc(left, middle);
	dc(middle + 1, right);
}

void Init(int N, int A[])
{
	size = N;
	for (int iElem = 0; iElem < N; iElem++)
		precalc[iElem][iElem] = A[iElem];
	dc(0, N);
}

int searchmid(int left, int right, int ql, int qr)
{
	int mid = (left + right) / 2;
	if (qr < mid)
		return searchmid(left, mid, ql, qr);
	if (ql > mid)
		return searchmid(mid + 1, right, ql, qr);
	return mid;
}

int Query(int L, int R)
{
	int mid = searchmid(0, size, L, R);
	if (L < mid)
		return Secret(precalc[L][mid - 1], precalc[mid][R]);
	return precalc[mid][R];
}

• Subtask 1: 100 / 100