Submission #171047

#	Time	Username	Problem	Language	Result	Execution time	Memory
171047		ZwariowanyMarcin	Secret (JOI14_secret)	C++14	100 / 100	657 ms	4496 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)
 
using namespace std;
 
int n;
int a[1024];
int val[1024][11];
 
void dc(int l, int r, int lvl) {
	if(l >= r) return;
	int m = (l + r) / 2;
	val[m][lvl] = a[m];
	for(int j = m - 1; l <= j; --j)
		val[j][lvl] = Secret(a[j], val[j + 1][lvl]);
	val[m + 1][lvl] = a[m + 1];
	for(int j = m + 2; j <= r; ++j)
		val[j][lvl] = Secret(val[j - 1][lvl], a[j]);
	dc(l, m, lvl + 1);
	dc(m + 1, r, lvl + 1);
}
 
void Init(int N, int A[]) {
	n = N;
	for(int i = 0; i < n; ++i)
		a[i] = A[i];
	dc(0, n - 1, 0);
}
 
int solve(int x, int y, int l, int r, int lvl = 0) {
	int m = (l + r) / 2;
	if(x <= m && m + 1 <= y) 
		return Secret(val[x][lvl], val[y][lvl]);
	if(y <= m)
		return solve(x, y, l, m, lvl + 1);
	return solve(x, y, m + 1, r, lvl + 1);
}
 
int Query(int l, int r) {
	if(l == r) return a[l];
	return solve(l, r, 0, n - 1);
}
 
/*int main() {
	int A[] = {1, 4, 7, 2, 5, 8, 3, 6};
	Init(8, A);
	cout << Query(0, 3) << endl;
	cout << Query(1, 7) << endl;
	cout << Query(5, 5) << endl;
	cout << Query(2, 4) << endl;
	
	
	
	return 0;
}
*/

• Subtask 1: 100 / 100