oj.uz

Submission #50855

# Submission time Handle Problem Language Result Execution time Memory
50855 2018-06-13T17:05:30 Z radoslav11 Secret (JOI14_secret) C++14
0 / 100
 756 ms 55328 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(suff[idx].back(), a[i]));
	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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 51960 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 844516862.
2 Incorrect 205 ms 52156 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 880320712.
3 Incorrect 223 ms 52276 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 808570902.
4 Incorrect 756 ms 54560 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 360218693.
5 Incorrect 654 ms 54808 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 529006930.
6 Incorrect 617 ms 54964 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 850129153.
7 Incorrect 629 ms 55088 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 194162714.
8 Incorrect 644 ms 55088 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 215212056.
9 Incorrect 738 ms 55108 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 836644132.
10 Incorrect 671 ms 55328 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 336488781.