Submission #956407

#	Time	Username	Problem	Language	Result	Execution time	Memory
956407		MinaRagy06	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	2778 ms	257772 KiB

potion

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz(x) (int) x.size()

const int N = 100'005, D = 505;
vector<vector<array<int, 2>>> gud[N];
vector<int> rem[N];
int mx[N];
set<array<int, 2>> adj[N];
int a[N], n, m;
void init(int _n, int d, int h[]) {
	n = _n;
	for (int i = 0; i < n; i++) {
		for (int j = 499; j >= 0; j--) {
			rem[i].push_back(j);
		}
		a[i] = h[i];
	}
}
void upd(int i, int j, int v, int t) {
	gud[i][j].push_back({v, t});
}
void curseChanges(int _m, int A[], int B[]) {
	m = _m;
	for (int i = 0; i < m; i++) {
		int u = A[i], v = B[i];
		auto it = adj[u].lower_bound({v, 0});
		if (it != adj[u].end() && (*it)[0] == v) {
			int x = (*it)[1];
			rem[u].push_back(x);
			adj[u].erase({v, x});

			it = adj[v].lower_bound({u, 0});
			x = (*it)[1];
			rem[v].push_back(x);
			adj[v].erase({u, x});
		} else {
			int x = rem[u].back();
			rem[u].pop_back();
			adj[u].insert({v, x});
			mx[u] = max(mx[u], x + 1);

			x = rem[v].back();
			rem[v].pop_back();
			adj[v].insert({u, x});
			mx[v] = max(mx[v], x + 1);
		}
	}
	for (int i = 0; i < n; i++) {
		adj[i].clear();
		rem[i].clear();
		for (int j = mx[i] - 1; j >= 0; j--) {
			rem[i].push_back(j);
		}
		gud[i].resize(mx[i]);
	}

	for (int i = 0; i < m; i++) {
		int u = A[i], v = B[i];
		auto it = adj[u].lower_bound({v, 0});
		if (it != adj[u].end() && (*it)[0] == v) {
			int x = (*it)[1];
			upd(u, x, -1, i + 1);
			rem[u].push_back(x);
			adj[u].erase({v, x});

			it = adj[v].lower_bound({u, 0});
			x = (*it)[1];
			upd(v, x, -1, i + 1);
			rem[v].push_back(x);
			adj[v].erase({u, x});
		} else {
			int x = rem[u].back();
			upd(u, x, a[v], i + 1);
			rem[u].pop_back();
			adj[u].insert({v, x});

			x = rem[v].back();
			upd(v, x, a[u], i + 1);
			rem[v].pop_back();
			adj[v].insert({u, x});
		}
	}
}
int question(int x, int y, int v) {
	vector<int> v1, v2;
	for (int j = 0; j < max(mx[x], mx[y]); j++) {
		if (j < mx[x]) {
			int l = 0, r = sz(gud[x][j]) - 1;
			while (l <= r) {
				int md = ((l + r) >> 1);
				if (gud[x][j][md][1] <= v) {
					l = md + 1;
				} else {
					r = md - 1;
				}
			}
			if (r >= 0 && gud[x][j][r][0] != -1) {
				v1.push_back(gud[x][j][r][0]);
			}
		}
		if (j < mx[y]) {
			int l = 0, r = sz(gud[y][j]) - 1;
			while (l <= r) {
				int md = ((l + r) >> 1);
				if (gud[y][j][md][1] <= v) {
					l = md + 1;
				} else {
					r = md - 1;
				}
			}
			if (r >= 0 && gud[y][j][r][0] != -1) {
				v2.push_back(gud[y][j][r][0]);
			}
		}
	}
	int ans = 1e9;
	if (v1.empty() || v2.empty()) {
		return ans;
	}
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	int ptr = 0;
	for (int i = 0; i < sz(v1); i++) {
		while (ptr + 1 < sz(v2) && v2[ptr + 1] <= v1[i]) {
			ptr++;
		}
		ans = min(ans, abs(v1[i] - v2[ptr]));
		if (ptr + 1 < sz(v2)) {
			ans = min(ans, abs(v1[i] - v2[ptr + 1]));
		}
	}
	return ans;
}
#ifdef MINA
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int _N = 6, _D = 5, U = 11;
	int H[] = {2, 42, 1000, 54, 68, 234};
	int A[] = {0, 2, 3, 3, 3, 1, 5, 0, 3, 1, 3};
	int B[] = {1, 0, 4, 5, 5, 3, 3, 5, 0, 3, 5};
	init(_N, _D, H);
	curseChanges(U, A, B);
	cout << question(0, 3, 4) << '\n';
	cout << question(3, 0, 8) << '\n';
	cout << question(0, 5, 5) << '\n';
	cout << question(3, 0, 11) << '\n';
	return 0;
}
#endif

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