Submission #137045

#	Time	Username	Problem	Language	Result	Execution time	Memory
137045		mosesmayer	Secret (JOI14_secret)	C++17	0 / 100	602 ms	18692 KiB

secret

#include "secret.h"

int spt[10][1005];
int a[1005];
bool asked[1005][1005]; int val[1005][1005];
int ask(int x, int y){
	if (asked[x][y]) return val[x][y];
	asked[x][y] = 1;
	return val[x][y] = Secret(x, y);
}
void rec(int l, int r, int d = 0){
	if (l == r){
		spt[d][l] = a[l];
		return;
	}
	int md = (l + r) >> 1;
	rec(l, md, d + 1); rec(md + 1, r, d + 1);
	int prv = a[md];
	spt[d][md] = a[md];
	for (int i = md - 1; i >= l; --i){
		spt[d][i] = ask(a[i], prv);
		prv = spt[d][i];
	}
	prv = a[md + 1];
	spt[d][md + 1] = a[md + 1];
	for (int i = md + 2; i <= r; i++){
		spt[d][i] = ask(prv, a[i]);
		prv = spt[d][i];
	}
}
int n;
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++){
		asked[i][i] = 1; val[i][i] = a[i];
	}
	rec(0, N - 1);
}

int ans(int i, int j, int l, int r, int d = 0){
	if (l == r) return spt[d][l];
	int md = (l + r) >> 1;
	if (j <= md) return ans(i, j, l, md, d + 1);
	else if (i >= md + 1) return ans(i, j, md+1, r, d+1);
	else {
		return ask(spt[d][i], spt[d][j]);
	}
}
int Query(int L, int R){
	return ans(L, R, 0, n - 1);
	return 0;
}

• Subtask 1: 0 / 100