oj.uz

Submission #50856

# Submission time Handle Problem Language Result Execution time Memory
50856 2018-06-13T17:07:10 Z radoslav11 Secret (JOI14_secret) C++14
100 / 100
 712 ms 55100 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 52588 KB Output is correct - number of calls to Secret by Init = 3324, maximum number of calls to Secret by Query = 1
2 Correct 225 ms 52700 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
3 Correct 212 ms 52700 KB Output is correct - number of calls to Secret by Init = 3341, maximum number of calls to Secret by Query = 1
4 Correct 635 ms 54992 KB Output is correct - number of calls to Secret by Init = 7483, maximum number of calls to Secret by Query = 1
5 Correct 656 ms 55036 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
6 Correct 663 ms 55036 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
7 Correct 712 ms 55052 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
8 Correct 641 ms 55100 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
9 Correct 636 ms 55100 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
10 Correct 687 ms 55100 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1