oj.uz

Submission #156982

# Submission time Handle Problem Language Result Execution time Memory
156982 2019-10-08T18:04:28 Z faremy Secret (JOI14_secret) C++14
100 / 100
 593 ms 8440 KB 
#include "secret.h"


const int MAXN = 1000;

int size = 0;
int precalc[MAXN][MAXN];


void dc(int left, int right)
{
	if (right - left <= 1)
		return;
	int middle = (left + right) / 2;

	for (int iElem = middle + 1; iElem < right; iElem++)
		precalc[middle][iElem] = Secret(precalc[middle][iElem - 1], precalc[iElem][iElem]);
	for (int iElem = middle - 2; iElem >= left; iElem--)
		precalc[iElem][middle - 1] = Secret(precalc[iElem][iElem], precalc[iElem + 1][middle - 1]);
	dc(left, middle);
	dc(middle + 1, right);
}

void Init(int N, int A[])
{
	size = N;
	for (int iElem = 0; iElem < N; iElem++)
		precalc[iElem][iElem] = A[iElem];
	dc(0, N);
}

int searchmid(int left, int right, int ql, int qr)
{
	int mid = (left + right) / 2;
	if (qr < mid)
		return searchmid(left, mid, ql, qr);
	if (ql > mid)
		return searchmid(mid + 1, right, ql, qr);
	return mid;
}

int Query(int L, int R)
{
	int mid = searchmid(0, size, L, R);
	if (L < mid)
		return Secret(precalc[L][mid - 1], precalc[mid][R]);
	return precalc[mid][R];
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 4472 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 167 ms 4524 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 168 ms 4444 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 583 ms 8396 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 586 ms 8440 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 586 ms 8264 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 593 ms 8356 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 587 ms 8312 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 588 ms 8344 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 590 ms 8396 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1