oj.uz

Submission #682126

# Submission time Handle Problem Language Result Execution time Memory
682126 2023-01-15T21:01:10 Z NK_ Secret (JOI14_secret) C++17
100 / 100
 417 ms 4332 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 = 1025;
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 121 ms 2384 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 116 ms 2360 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 117 ms 2368 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 410 ms 4284 KB Output is correct - number of calls to Secret by Init = 7991, maximum number of calls to Secret by Query = 1
5 Correct 412 ms 4300 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
6 Correct 410 ms 4324 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
7 Correct 411 ms 4320 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
8 Correct 413 ms 4312 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
9 Correct 414 ms 4208 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
10 Correct 417 ms 4332 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1