Submission #301688

#	Time	Username	Problem	Language	Result	Execution time	Memory
301688		E869120	Secret (JOI14_secret)	C++14	100 / 100	516 ms	8344 KiB

secret

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

int N;
int A[1009];
int V[1009][1009];
int Value;

void solve(int cl, int cr) {
	if (cr - cl == 1) return;
	int cm = (cl + cr) / 2;
	
	// LFT
	int cur = A[cm - 1];
	for (int i = cm - 2; i >= cl; i--) {
		cur = Secret(A[i], cur);
		V[i][cm - 1] = cur;
	}
	
	// RHT
	int cur2 = A[cm];
	for (int i = cm + 1; i < cr; i++) {
		cur2 = Secret(cur2, A[i]);
		V[cm][i] = cur2;
	}
	
	// SAIKI
	solve(cl, cm);
	solve(cm, cr);
}

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

void dfs(int l, int r, int a, int b) {
	int m = (a + b) / 2;
	if (r <= a || b <= l) return;
	if (l < m && m < r) {
		int p1 = V[l][m - 1];
		int p2 = V[m][r - 1];
		Value = Secret(p1, p2);
		return;
	}
	dfs(l, r, a, m);
	dfs(l, r, m, b);
}

int Query(int L, int R) {
	if (L == R) return A[L];
	Value = -1;
	dfs(L, R + 1, 0, N);
	return Value;
}

• Subtask 1: 100 / 100