oj.uz

Submission #338577

# Submission time Handle Problem Language Result Execution time Memory
338577 2020-12-23T12:54:32 Z Drew_ Secret (JOI14_secret) C++14
100 / 100
 529 ms 8428 KB 
#include "secret.h"


int const MAX = 1e3 + 7;

int len;
int data[MAX][MAX];

void rc(int l, int r, int A[])
{
	if (l == r)
	{
		data[l][l] = A[l];
		return;
	}

	int mid = (l + r) / 2;
	rc(l, mid, A);
	rc(mid+1, r, A);

	for (int i = mid-1; i >= l; --i)
		data[i][mid] = Secret(A[i], data[i+1][mid]);
	for (int i = mid+2; i <= r; ++i)
		data[mid+1][i] = Secret(data[mid+1][i-1], A[i]);
	return;
}

void Init(int N, int A[]) {
	len = N;
	rc(0, N-1, A);
}

int query_rc(int l, int r, int p, int q)
{
	if (l == r)
		return data[l][l];

	int mid = (l + r) / 2;
	if (mid == q)
		return data[p][mid];
	if (mid+1 == p)
		return data[mid+1][q];

	if (p <= mid && mid+1 <= q)
		return Secret(data[p][mid], data[mid+1][q]);

	if (q < mid)
		return query_rc(l, mid, p, q);
	return query_rc(mid+1, r, p, q);
}

int Query(int L, int R) {
	return query_rc(0, len-1, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 4460 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 149 ms 4460 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 506 ms 8404 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 505 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 517 ms 8172 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 513 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 529 ms 8272 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 519 ms 8172 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 519 ms 8428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1