oj.uz

Submission #548868

# Submission time Handle Problem Language Result Execution time Memory
548868 2022-04-14T15:29:11 Z rainboy Secret (JOI14_secret) C
100 / 100
 499 ms 4424 KB 
#include "secret.h"

#define N	1000
#define M	10000

int bb[M], *ptr, *cc[N], n;

void solve(int *aa, int l, int r) {
	int m, i;

	if (l > r)
		return;
	m = (l + r) / 2;
	cc[m] = ptr, ptr += r - l + 1;
	cc[m][m - l] = aa[m];
	for (i = m - 1; i >= l; i--)
		cc[m][i - l] = Secret(aa[i], cc[m][i + 1 - l]);
	if (l < r) {
		cc[m][m + 1 - l] = aa[m + 1];
		for (i = m + 2; i <= r; i++)
			cc[m][i - l] = Secret(cc[m][i - 1 - l], aa[i]);
	}
	solve(aa, l, m - 1), solve(aa, m + 2, r);
}

void Init(int n_, int *aa) {
	n = n_, ptr = bb, solve(aa, 0, n - 1);
}

int query(int l, int r, int ql, int qr) {
	int m = (l + r) / 2;

	if (qr == m)
		return cc[m][ql - l];
	if (ql == m + 1)
		return cc[m][qr - l];
	if (ql <= m && m + 1 <= qr)
		return Secret(cc[m][ql - l], cc[m][qr - l]);
	return qr < m ? query(l, m - 1, ql, qr) : query(m + 2, r, ql, qr);
}

int Query(int l, int r) {
	return query(0, n - 1, l, r);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 2344 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 142 ms 2428 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 135 ms 2408 KB Output is correct - number of calls to Secret by Init = 3100, maximum number of calls to Secret by Query = 1
4 Correct 448 ms 4424 KB Output is correct - number of calls to Secret by Init = 6988, maximum number of calls to Secret by Query = 1
5 Correct 454 ms 4420 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
6 Correct 478 ms 4300 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
7 Correct 446 ms 4332 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
8 Correct 460 ms 4348 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
9 Correct 461 ms 4328 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
10 Correct 499 ms 4304 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1