Submission #605826

#	Time	Username	Problem	Language	Result	Execution time	Memory
605826		SanguineChameleon	Secret (JOI14_secret)	C++14	100 / 100	465 ms	8328 KiB

secret

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

const int ms = 1e3 + 20;
int n;
int a[ms];
int res[ms][ms];

void build(int lt, int rt) {
	if (lt == rt) {
		res[lt][lt] = a[lt];
		return;
	}
	int mt = (lt + rt) / 2;
	if (lt <= mt - 1) {
		res[mt - 1][mt - 1] = a[mt - 1];
		for (int i = mt - 2; i >= lt; i--) {
			res[i][mt - 1] = Secret(a[i], res[i + 1][mt - 1]);
		}
		build(lt, mt - 1);
	}
	res[mt][mt] = a[mt];
	if (mt + 1 <= rt) {
		for (int i = mt + 1; i <= rt; i++) {
			res[mt][i] = Secret(res[mt][i - 1], a[i]);
		}
		build(mt + 1, rt);
	}
}

int solve(int lt, int rt, int ql, int qr) {
	int mt = (lt + rt) / 2;
	if (ql == mt) {
		return res[mt][qr];
	}
	if (ql < mt && mt <= qr) {
		return Secret(res[ql][mt - 1], res[mt][qr]);
	}
	if (qr < mt) {
		return solve(lt, mt - 1, ql, qr);
	}
	return solve(mt + 1, rt, ql, qr);
}

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

int Query(int L, int R) {
	return solve(0, n - 1, L, R);
}

• Subtask 1: 100 / 100