oj.uz

Submission #704613

# Submission time Handle Problem Language Result Execution time Memory
704613 2023-03-02T12:27:41 Z dubabuba Secret (JOI14_secret) C++14
100 / 100
 439 ms 8312 KB 
#include "secret.h"

const int mxn = 1010;
int n, range[mxn][mxn];

void build(int l, int r, int a[]) {
	if(l == r) return;

	// cout << "building: " << l << ' ' << r << '\n';
	int m = (l + r) / 2;
	int M = (l + r) / 2 + 1;
	// cout << "    > " << m << ' ' << M << '\n';

	range[m][m] = a[m];
	range[M][M] = a[M];

	for(int i = M + 1; i <= r; i++)
		range[M][i] = Secret(range[M][i - 1], a[i]);
	for(int i = m - 1; i >= l; i--)
		range[i][m] = Secret(a[i], range[i + 1][m]);

	build(l, m, a);
	build(M, r, a);
}

void Init(int n, int a[]) {
	::n = n;
	build(0, n - 1, a);
}

int Query(int L, int R) {
	int l = 0, r = n - 1;

	// cout << "e " << L << ' ' << R << '\n';
	// cout << range[L][R] << '\n';
	while(r - l > 1) {
		int m = (l + r) / 2;
		int M = (l + r) / 2 + 1;

		if(L <= m && M <= R) {
			return Secret(range[L][m], range[M][R]);
		}
		if(R <= m) r = m;
		if(M <= L) l = M;
	}
	// cout << "sussy baka " << range[L][R] << '\n';
	return range[L][R];
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 4372 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 119 ms 4320 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 121 ms 4364 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 421 ms 8212 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 439 ms 8200 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 422 ms 8160 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 433 ms 8292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 424 ms 8140 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 418 ms 8164 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 429 ms 8312 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1