Submission #296222

#	Time	Username	Problem	Language	Result	Execution time	Memory
296222		patrikpavic2	Secret (JOI14_secret)	C++17	100 / 100	591 ms	8800 KiB

secret

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

const int N = 1e3 + 50;

int n, A[N], Q[N][N];

void calc(int l, int r){
	if(l + 2 > r) return;
	int mid = (l + r) / 2;
	for(int i = mid - 1;i >= l;i--)
		Q[i][mid] = Secret(A[i], Q[i + 1][mid]);
	for(int i = mid + 2;i <= r;i++)
		Q[mid + 1][i] = Secret(Q[mid + 1][i - 1], A[i]);
	calc(l, mid);
	calc(mid + 1, r);
}

void Init(int nn, int AA[]) {
	n = nn; memset(Q, -1, sizeof(Q));
	for(int i = 0;i < n;i++){
		A[i] = AA[i]; Q[i][i] = A[i];
	}
	calc(0, n - 1);
}

int Query(int l, int r) {
	if(Q[l][r] != -1)
		return Q[l][r];
	for(int k = l;k < r;k++){
		if(Q[l][k] != -1 && Q[k + 1][r] != -1)
			return Secret(Q[l][k], Q[k + 1][r]);
	}
	return 0;
}

• Subtask 1: 100 / 100