Submission #1179939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179939		NK_	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	1908 ms	74360 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;
vpi 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, pi e) {
	seg[x].pb(e);
	swap(e.f, e.s);
	seg[x].pb(e);
}

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) {
		int pos = lower_bound(begin(seg[p]), end(seg[p]), mp(x, -1)) - begin(seg[p]);
		while(pos < sz(seg[p])) {
			if (seg[p][pos].f == x) adj.pb(H[seg[p][pos].s]);
			else break;
			pos++;
		}
	}

	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 + 1;
		else {
			add(L[e], i, e);
			L.erase(e);
		}
	}

	for(auto& e : L) {
		add(e.s, m, e.f);
	}

	for(int i = 1; i < 2 * nax; i++) sort(begin(seg[i]), end(seg[i]));
	
	// 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));
	
	// for(auto& h : hx) cout << h << " ";
	// cout << endl;

	// for(auto& h : hy) cout << h << " ";
	// cout << endl;

	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: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30