Submission #156547

#	Time	Username	Problem	Language	Result	Execution time	Memory
156547		Saboon	Secret (JOI14_secret)	C++14	100 / 100	638 ms	8528 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000 + 10;

int a[maxn][maxn];
int h[maxn];

void divide(int L, int R, int nowh = 0){
	if (L + 1 == R)
		return;
	int mid = (L + R) >> 1;
	h[mid] = nowh;
	for (int i = mid; i < R; i++)
		if (a[mid][i] == -1)
			a[mid][i] = Secret(a[mid][i - 1], a[i][i]);
	for (int i = mid - 1; i >= L; i--)
		if (a[i][mid - 1] == -1)
			a[i][mid - 1] = Secret(a[i][i], a[i + 1][mid - 1]);
	divide(L, mid, nowh + 1);
	divide(mid, R, nowh + 1);
}

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

int Query(int L, int R) {
	int mid = L;
	for (int i = L; i <= R + 1; i++)
		if (h[i] < h[mid])
			mid = i;
	if (mid == L or mid == R + 1)
		return a[L][R];
	return Secret(a[L][mid - 1], a[mid][R]);
}

• Subtask 1: 100 / 100