Submission #1179918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179918		NK_	The Potion of Great Power (CEOI20_potion)	C++17	0 / 100	2078 ms	327680 KiB

potion

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

#define f first
#define s second
#define mp make_pair

using pi = pair<int, int>;
template<class T> using V = vector<T>;
using vi = V<int>;
using vpi = V<pi>;

const int nax = (1 << 18);
const int INF = 1e9;
map<int, vi> seg[2 * nax];
	
int N, D; vi H;
void init(int n, int d, int h[]) {
	N = n, D = d; H = vi(N); 
	for(int i = 0; i < N; i++) H[i] = h[i];
	// cout << "INIT" << endl;
}

void ae(int x, const pi &e) {
	seg[x][e.f].pb(H[e.s]);
	seg[x][e.s].pb(H[e.f]);
}

void add(int l, int r, const pi &e) {
	for(l += nax, r += nax + 1; l < r; l /= 2, r /= 2) {
		if (l & 1) ae(l++, e);
		if (r & 1) ae(--r, e);
	}
}

vi get(int p, int x) { 
	vi adj; for(p += nax; p; p /= 2) {
		const vi &ADJ = seg[p][x];
		adj.insert(end(adj), begin(ADJ), end(ADJ));
	}

	return adj;
}

void curseChanges(int m, int a[], int b[]) {
	map<pi, int> L;
	for(int i = 0; i < m; i++) {
		pi e = minmax(a[i], b[i]);
		if (L.find(e) == L.end()) L[e] = i;
		else {
			add(L[e], i, e);
			L.erase(e);
		}
	}

	for(auto& e : L) {
		add(e.s, m, e.f);
	}
	
	// cout << "UPDATES" << endl;
}

int question(int x, int y, int v) {
	// cout << "QRY: " << x << " " << y << " " << v << endl;
	vi hx = get(v, x), hy = get(v, y);
	sort(begin(hx), end(hx)); sort(begin(hy), end(hy));

	int ans = INF;
	for(int i = 0, j = 0; i < sz(hx); i++) {
		while(j < sz(hy) && hx[i] > hy[j]) j++;
		if (j < sz(hy)) ans = min(ans, hy[j] - hx[i]);
		if (j) ans = min(ans, hx[i] - hy[j - 1]);
	}

	return ans;
}

// Breathe In, Breathe Out

• Subtask 1: 0 / 0
• Subtask 2: 0 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 30