oj.uz

Submission #416117

# Submission time Handle Problem Language Result Execution time Memory
416117 2021-06-02T02:17:52 Z mbfibat Secret (JOI14_secret) C++17
100 / 100
 603 ms 4404 KB 
#include "secret.h"
#include <iostream>

using namespace std;

int a[1001];
int val[11][1001], mask[1001];

int comb(int x, int y) {
	return Secret(x, y);
}

void init(int l, int r, int lev) {
	if (l == r) 
		return;

	int mi = (l + r) / 2;
	val[lev][mi] = a[mi];
	for (int i = mi - 1; i >= l; i--)
		val[lev][i] = comb(a[i], val[lev][i + 1]);

	val[lev][mi + 1] = a[mi + 1];
	for (int i = mi + 2; i <= r; i++)
		val[lev][i] = comb(val[lev][i - 1], a[i]);
	for (int i = mi + 1; i <= r; i++)
		mask[i] |= (1 << lev);
	init(l, mi, lev + 1);
	init(mi + 1, r, lev + 1);
}

void Init(int N, int A[]) {
	for (int i = 1; i <= N; i++)
		a[i] = A[i - 1];
	init(1, N, 0);
}

int Query(int L, int R) {
	L++, R++;
	if (L == R) return a[L];
	else {
		int lev = __builtin_ctz(mask[L] ^ mask[R]);
		return Secret(val[lev][L], val[lev][R]);
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 2468 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 151 ms 2404 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 164 ms 2508 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 578 ms 4304 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 573 ms 4400 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 553 ms 4404 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 589 ms 4292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 603 ms 4372 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 601 ms 4392 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 529 ms 4292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1