Submission #50856

#	Time	Username	Problem	Language	Result	Execution time	Memory
50856		radoslav11	Secret (JOI14_secret)	C++14	100 / 100	712 ms	55100 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"
//#include "Lgrader.cpp"
#define endl '\n'

//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

int a[MAXN], n;
map<pair<int, int>, int> memo; 

int eval(int x, int y)
{
	//if(x > y) swap(x, y);
	if(memo.count({x, y})) return memo[{x, y}];
	return memo[{x, y}] = Secret(x, y);
}

vector<int> pref[MAXN], suff[MAXN];

void rec(int l, int r, int idx)
{
	if(l == r) return;

	int mid = (l + r) >> 1;
	rec(l, mid, 2 * idx + 1);
	rec(mid + 1, r, 2 * idx + 2);

	suff[idx].assign(1, a[mid]);
	pref[idx].assign(1, a[mid + 1]);

	for(int i = mid - 1; i >= l; i--) suff[idx].push_back(eval(a[i], suff[idx].back()));
	for(int i = mid + 2; i <= r; i++) pref[idx].push_back(eval(pref[idx].back(), a[i]));
}

void Init(int N, int A[])
{
	memo.clear();
	
	n = N;
	for(int i = 0; i < n; i++)
		a[i] = A[i];

	rec(0, n - 1, 0);
}

int query(int ql, int qr, int l, int r, int idx)
{
	int mid = (l + r) >> 1;
	if(qr <= mid) return query(ql, qr, l, mid, 2 * idx + 1);
	if(mid < ql) return query(ql, qr, mid + 1, r, 2 * idx + 2);
	return eval(suff[idx][mid - ql], pref[idx][qr - mid - 1]);	
}

int Query(int l, int r)
{
	if(l == r) return a[l];
	return query(l, r, 0, n - 1, 0);
}

• Subtask 1: 100 / 100