Submission #703776

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
703776	2023-02-28T11:09:09 Z	dubabuba	Secret (JOI14_secret)	C++14	0 / 100	481 ms	4520 KB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int mxn = 2e5 + 10;
int n, a[mxn], sus[mxn * 4];
map<pii, int> mp;

bool inmap(int x, int y) {
	if(x > y) swap(x, y);
	auto it = mp.find(make_pair(x, y));
	return it != mp.end();
}

int pushmap(int x, int y) {
	if(x > y) swap(x, y);
	if(inmap(x, y)) return mp[make_pair(x, y)];
	return mp[make_pair(x, y)] = Secret(x, y);
}

void build(int id, int tl, int tr) {
	if(tl == tr) {
		sus[id] = a[tl];
		return;
	}

	int tm = (tl + tr) / 2;
	build(id * 2 + 1, tl, tm);
	build(id * 2 + 2, tm + 1, tr);
	sus[id] = pushmap(sus[id * 2 + 1], sus[id * 2 + 2]);
}

int query(int id, int tl, int tr, int l, int r) {
	if(tl == l && r == tr) return sus[id];
	int tm = (tl + tr) / 2;
	if(r <= tm) return query(id * 2 + 1, tl, tm, l, r);
	if(tm < l) return query(id * 2 + 2, tm + 1, tr, l, r);
	return pushmap(query(id * 2 + 1, tl, tm, l, tm), query(id * 2 + 2, tm + 1, tr, tm + 1, r));
}

void Init(int N, int A[]) {
	n = N;
	for(int i = 0; i < n; i++)
		a[i] = A[i];
	build(0, 0, N - 1);
}

int Query(int L, int R) {
	return query(0, 0, n - 1, L, R);
}

Subtask #1

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	108 ms	2368 KB	Wrong Answer: Query(222, 254) - expected : 34031541, actual : 571570413.
2	Incorrect	112 ms	2332 KB	Wrong Answer: Query(60, 375) - expected : 669221184, actual : 922914816.
3	Incorrect	116 ms	2436 KB	Wrong Answer: Query(211, 401) - expected : 674373968, actual : 429027664.
4	Incorrect	414 ms	4276 KB	Wrong Answer: Query(90, 497) - expected : 397934825, actual : 843251958.
5	Incorrect	432 ms	4272 KB	Wrong Answer: Query(587, 915) - expected : 752404486, actual : 14682184.
6	Incorrect	481 ms	4256 KB	Wrong Answer: Query(738, 741) - expected : 983692994, actual : 850129153.
7	Incorrect	417 ms	4520 KB	Wrong Answer: Query(84, 976) - expected : 742463504, actual : 800201810.
8	Incorrect	423 ms	4300 KB	Wrong Answer: Query(58, 987) - expected : 20022464, actual : 213936592.
9	Incorrect	417 ms	4348 KB	Wrong Answer: Query(33, 967) - expected : 676869696, actual : 286271812.
10	Incorrect	430 ms	4380 KB	Wrong Answer: Query(116, 961) - expected : 68487362, actual : 6251457.