Submission #375352

#	Time	Username	Problem	Language	Result	Execution time	Memory
375352		peijar	비밀 (JOI14_secret)	C++17	100 / 100	524 ms	8684 KiB

secret

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

const int MAXN = 1000;
int queries[MAXN][MAXN];
int values[MAXN];
int nbElem;

int solve(int deb, int fin, int reqDeb, int reqFin)
{
	if (deb == fin)
		return values[deb];
	int mid = (deb + fin) / 2;
	if (reqFin <= mid)
		return solve(deb, mid, reqDeb, reqFin);
	if (reqDeb > mid)
		return solve(mid+1, fin, reqDeb, reqFin);
	// reqDeb <= mid < reqFin
	return Secret(queries[reqDeb][mid], queries[mid+1][reqFin]);
}

void calcAllQueriesLeft(int deb, int fin, int curL)
{
	if (curL == fin) return ;
	int mid = (deb + fin) / 2;
	if (curL <= mid)
	{
		assert(queries[curL][mid] != -1);
		assert(queries[mid+1][fin] != -1);
		queries[curL][fin] = Secret(queries[curL][mid], queries[mid+1][fin]);
		calcAllQueriesLeft(deb, fin, curL+1);
	}
	else
		calcAllQueriesLeft(mid+1, fin, curL);
}

void calcAllQueriesRight(int deb, int fin, int cur)
{
	if (cur == deb) return ;
	int mid = (deb + fin) / 2;
	if (cur > mid)
	{
		assert(queries[deb][mid]!= -1);
		assert(queries[mid+1][cur] != -1);
		queries[deb][cur] = Secret(queries[deb][mid], queries[mid+1][cur]);
		calcAllQueriesRight(deb, fin, cur-1);
	}
	else
		calcAllQueriesRight(deb, mid, cur);
}

void calcQueries(int deb, int fin)
// Calcule toutes les requetes [i, (deb+fin)/2] et [(deb+fin)/2+1, i]
{
	if (deb >= fin)
		return ;
	int mid = (deb + fin) / 2;
	calcQueries(deb,mid);
	calcQueries(mid+1, fin);
	calcAllQueriesLeft(deb, mid, deb);
	calcAllQueriesRight(mid+1, fin, fin);
}

void Init(int N, int A[]) {
	nbElem = N;
	for(int i(0); i < N; ++i)
		for (int j(0); j < N; ++j)
			queries[i][j] = -1;
	for (int i(0); i < N; ++i)
		values[i] = queries[i][i] = A[i];
	calcQueries(0, N-1);
}

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

• Subtask 1: 100 / 100