oj.uz

Submission #682125

# Submission time Handle Problem Language Result Execution time Memory
682125 2023-01-15T20:55:41 Z NK_ Secret (JOI14_secret) C++17
100 / 100
 438 ms 4444 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

#define nl '\n'


const int nax = 1005;
const int kax = 32 - __builtin_clz(nax);
int stor[nax][kax];
int N, M;
vector<int> A;

int comb(int a, int b) { 
	if (a == -1) return b;
	if (b == -1) return a;
	return Secret(a, b);
}

void fill(int l, int r, int ind) {
	if (ind < 0) return;
	int m = (l+r)/2, cur;

	// cout << l << " " << m << " " << r << " (" << ind << ")" << endl;

	stor[m-1][ind] = cur = A[m-1]; 
	for(int i = m-2; i >= l; i--) stor[i][ind] = cur = comb(A[i], cur);

	stor[m][ind] = cur = A[m];
	for(int i = m+1; i < r; i++) stor[i][ind] = cur = comb(cur, A[i]);

	fill(l, m, ind-1); fill(m, r, ind-1);
}


void Init(int _N, int _A[]) {
	N = _N;
	M = 1; while((1<<M) < N) ++M;

	A = vector<int>((1<<M), -1);
	for(int i = 0; i < N; i++) A[i] = _A[i];

	fill(0, (1<<M), M-1);
	// cerr << "DONE" << endl;
}

int Query(int L, int R) {
	if (L == R) return A[L];
	int t = 31 - __builtin_clz(L ^ R);
	return comb(stor[L][t], stor[R][t]);
};

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 2380 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 2424 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 122 ms 2460 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 438 ms 4444 KB Output is correct - number of calls to Secret by Init = 7991, maximum number of calls to Secret by Query = 1
5 Correct 420 ms 4292 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
6 Correct 413 ms 4304 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
7 Correct 413 ms 4284 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
8 Correct 426 ms 4380 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
9 Correct 429 ms 4312 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
10 Correct 415 ms 4396 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1