oj.uz

Submission #375352

# Submission time Handle Problem Language Result Execution time Memory
375352 2021-03-09T09:45:32 Z peijar Secret (JOI14_secret) C++17
100 / 100
 524 ms 8684 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 4484 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 144 ms 4584 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 144 ms 4460 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 516 ms 8684 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 513 ms 8428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 516 ms 8556 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 519 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 503 ms 8428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 524 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 511 ms 8428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1