| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1228007 | Turkhuu | The Potion of Great Power (CEOI20_potion) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
const int C = 95;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, D, U, Q;
cin >> N >> D >> U >> Q;
vector<int> h(N);
for (auto& x : h) cin >> x;
vector<vector<array<int, 3>>> upds(N);
vector<set<int>> cur(N);
vector<vector<vector<int>>> adj(N);
auto upd = [&](int x, int y, int d) {
if (cur[x].count(y)) {
cur[x].erase(y);
upds[x].push_back({d, y, -1});
} else {
cur[x].insert(y);
upds[x].push_back({d, y, 1});
}
if (upds[x].size() % C == 0) {
adj[x].push_back({});
for (int y : cur[x])
adj[x].back().push_back(y);
}
};
FOR(i, 0, U - 1) {
int x, y;
cin >> x >> y;
upd(x, y, i), upd(y, x, i);
}
vector<bool> seen(N);
auto get = [&](int x, int d) {
int n = lower_bound(upds[x].begin(), upds[x].end(), array<int, 3>{d, -1, -1}) - upds[x].begin();
vector<int> ans;
ROF(i, n - 1, n / C * C) {
auto [_, y, z] = upds[x][i];
if (!seen[y]) {
seen[y] = 1;
if (z == 1)
ans.push_back(h[y]);
}
}
if (n >= C)
for (int y : adj[x][n / C - 1])
if (!seen[y])
ans.push_back(h[y]);
FOR(i, n / C * C, n - 1) seen[upds[x][i][1]] = 0;
return ans;
};
while (Q--) {
int x, y, d;
cin >> x >> y >> d;
auto hx = get(x, d);
auto hy = get(y, d);
sort(hx.begin(), hx.end());
sort(hy.begin(), hy.end());
int nx = hx.size(), ny = hy.size(), j = -1, ans = 1e9;
FOR(i, 0, nx - 1) {
while (j + 1 < ny && hy[j + 1] <= hx[i]) j++;
if (j >= 0) ans = min(ans, hx[i] - hy[j]);
if (j + 1 < ny) ans = min(ans, hy[j + 1] - hx[i]);
}
cout << ans << endl;
}
return 6/22;
}