oj.uz

Submission #415566

# Submission time Handle Problem Language Result Execution time Memory
415566 2021-06-01T08:43:24 Z mbfibat Secret (JOI14_secret) C++17
100 / 100
 571 ms 4348 KB 
#include "secret.h"
#include <iostream>

using namespace std;

int a[1001];
int val[1001][11], 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[mi][lev] = a[mi];
	for (int i = mi - 1; i >= l; i--)
		val[i][lev] = comb(a[i], val[i + 1][lev]);

	val[mi + 1][lev] = a[mi + 1];
	for (int i = mi + 2; i <= r; i++)
		val[i][lev] = comb(val[i - 1][lev], 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[L][lev], val[R][lev]);
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 2348 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 148 ms 2304 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 150 ms 2452 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 520 ms 4300 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 571 ms 4272 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 554 ms 4208 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 527 ms 4304 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 563 ms 4256 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 560 ms 4348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 544 ms 4316 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1