Submission #1263949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263949		wedonttalkanymore	Secret (JOI14_secret)	C++20	100 / 100	343 ms	8340 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MAXN = 1e3 + 5, inf = 1e9, mod = 1e9 + 7, block = 320, lim = 16;

int a[MAXN];
int n;
int dp[MAXN][MAXN];

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

void Init(int N, int A[]) {
	n = N;
	for (int i = 1; i <= n; i++) a[i] = A[i - 1];
	dnc(1, n);
}

int make(int l, int r, int &L, int &R) {
	if (l == r) return a[l];
	int mid = (l + r) / 2;
	if (R <= mid) return make(l, mid, L, R);
	if (L > mid) return make(mid + 1, r, L, R);
	int leftVal = dp[mid][L];
	int rightVal = dp[mid + 1][R];
	return Secret(leftVal, rightVal);
}

int Query(int L, int R) {
	L++;
	R++;
	return make(1, n, L, R);
}

• Subtask 1: 100 / 100