Submission #375337

#	Time	Username	Problem	Language	Result	Execution time	Memory
375337		peijar	Secret (JOI14_secret)	C++17	0 / 100	536 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 calcQueries(int deb, int fin)
// Calcule toutes les requetes [i, (deb+fin)/2] et [(deb+fin)/2+1, i]
{
	if (deb >= fin)
		return 0;
	int mid = (deb + fin) / 2;
	int ret = calcQueries(deb,mid) + calcQueries(mid+1, fin) + fin - deb-1;
	int mid2 = (deb + mid) / 2;
	for (int i(deb); i < mid; ++i)
		if (i <= mid2)
		{
			queries[i][mid] = Secret(queries[i][mid2], queries[mid2+1][mid]);
			ret++;
		}
	int mid3 = (mid + 1 + fin) / 2;
	for (int i(mid+2); i <= fin; ++i)
		if (i > mid3)
		{
			queries[mid+1][i] = Secret(queries[mid+1][mid3], queries[mid3+1][i]);
			ret++;
		}
	return ret;
}

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 Init(int N, int A[]) {
	nbElem = N;
	for (int i(0); i < N; ++i)
		values[i] = queries[i][i] = A[i];
	cerr << "nombre de requetes : " << calcQueries(0, N-1) << endl;
}

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

• Subtask 1: 0 / 100