Submission #682125

#	Time	Username	Problem	Language	Result	Execution time	Memory
682125		NK_	Secret (JOI14_secret)	C++17	100 / 100	438 ms	4444 KiB

secret

// 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 / 100