Submission #703776

#	Time	Username	Problem	Language	Result	Execution time	Memory
703776		dubabuba	Secret (JOI14_secret)	C++14	0 / 100	481 ms	4520 KiB

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 / 100