| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1212002 | miss_robot | The Potion of Great Power (CEOI20_potion) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int N = 1e5, U = 2e5+1, R = 450, INF = 1e9;
int n, d, u, q;
int h[N], snd[N], dns[N];
set< pair<int, int> > g[R];
pair<int, int> c[U];
int main(){
cin >> n >> d >> u >> q;
for(int i = 0; i < n; i++) cin >> h[i];
for(int i = 0; i < n; i++) snd[i] = i;
sort(snd, snd+n, [&](int a, int b){return h[a]<h[b];});
for(int i = 0; i < n; i++) dns[snd[i]] = i;
sort(h, h+n);
set< pair<int, int> > active;
for(int i = 1, x, y; i <= u; i++){
cin >> x >> y;
x = dns[x], y = dns[y];
if(x > y) swap(x, y);
c[i] = {x, y};
if(active.count({x, y})) active.erase({x, y});
else active.insert({x, y});
if(!(i%R)) g[i/R] = active;
}
for(int i = 0, x, y, v; i < q; i++){
cin >> x >> y >> v;
x = dns[x], y = dns[y];
active = g[v/R];
for(int j = v/R*R; j <= v; j++){
if(active.count(c[j])) active.erase(c[j]);
else active.insert(c[j]);
}
vector<int> gx, gy;
for(auto &t : active){
if(t.first == x || t.second == x) gx.push_back(t.first^t.second^x);
if(t.first == y || t.second == y) gy.push_back(t.first^t.second^y);
}
sort(gy.begin(), gy.end());
int sol = INF;
for(int t : gx){
int j = upper_bound(gy.begin(), gy.end(), t)-gy.begin();
if(j < (int)gy.size()) sol = min(sol, h[gy[j]] - h[t]);
if(j--) sol = min(sol, h[t] - h[gy[j]]);
}
cout << sol << endl;
}
}