oj.uz

Submission #85563

# Submission time Handle Problem Language Result Execution time Memory
85563 2018-11-20T23:34:39 Z KCSC Secret (JOI14_secret) C++14
0 / 100
 613 ms 5696 KB 
#include <bits/stdc++.h>
using namespace std;

int Secret(int x, int y);
void Init(int n, int arr[]);
int Query(int le, int ri);
/*
int Secret(int x, int y) {
	return x xor y xor 13; }
*/
int secret(int x, int y) {
	static map<pair<int, int>, int> mmp;
	if (mmp.find(make_pair(x, y)) != mmp.end()) {
		return mmp[make_pair(x, y)]; }
	else
		return (mmp[make_pair(x, y)] = Secret(x, y)); }

const int DIM = 1005;
vector<int> lef[DIM * 4], rig[DIM * 4];

void build(int nd, int le, int ri, int arr[]) {
	if (le != ri) {
		int md = (le + ri) / 2;
		build(nd * 2, le, md, arr);	
		build(nd * 2 + 1, md + 1, ri, arr); }
	lef[nd].resize(ri - le + 1); lef[nd][0] = arr[le];
	rig[nd].resize(ri - le + 1); rig[nd][ri - le] = arr[ri];	 
	if (le != ri and nd != 1) {
		int md = (le + ri) / 2;
		for (int i = 0; i <= ri - le; ++i) {
			lef[nd][i] = (i <= md - le) ? lef[nd * 2][i] : secret(lef[nd][i - 1], arr[le + i]); }
		for (int i = ri - le - 1; i >= 0; --i) {
			rig[nd][i] = (i >  md - le) ? rig[nd * 2 + 1][i - (md + 1)] : secret(arr[le + i], rig[nd][i + 1]); } } }  
		

int query(int nd, int le, int ri, int st, int en) {
	if (le == ri) {
		return lef[nd][0]; }
	else {
		int md = (le + ri) / 2;
		if (en <= md) {
			return query(nd * 2, le, md, st, en); }
		if (md <  st) {
			return query(nd * 2 + 1, md + 1, ri, st, en); }
		return secret(rig[nd * 2][st - le], lef[nd * 2 + 1][en - (md + 1)]); } } 

int _n;
void Init(int n, int arr[]) {
	build(1, 0, n - 1, arr); _n = n; }

int Query(int le, int ri) {
	return query(1, 0, _n - 1, le, ri); }
/*
int arr[10];

int main(void) {
#ifdef HOME
	freopen("secret.in", "r", stdin);
	freopen("secret.out", "w", stdout);
#endif
	int n; cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> arr[i]; }
	Init(n, arr);
	int m; cin >> m;
	while (m--) {
		int le, ri; cin >> le >> ri;
		int val = arr[le];
		for (int i = le + 1; i <= ri; ++i) {
			val = Secret(val, arr[i]); }
		cout << Query(le, ri) << " " << val << "\n"; }
	return 0; }	
*/

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 2972 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 839924963.
2 Incorrect 167 ms 3040 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 550144200.
3 Incorrect 160 ms 3040 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 539361598.
4 Incorrect 585 ms 5280 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 924434547.
5 Incorrect 590 ms 5400 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 358221838.
6 Incorrect 594 ms 5488 KB Wrong Answer: Query(200, 208) - expected : 277813445, actual : 3875264.
7 Incorrect 609 ms 5488 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 265855090.
8 Incorrect 589 ms 5696 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 293979208.
9 Incorrect 613 ms 5696 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 277088193.
10 Incorrect 590 ms 5696 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 7661704.