| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 966842 | anton | The Potion of Great Power (CEOI20_potion) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
struct Node{
int subsz= 0, id = -1;
int l = -1, r = -1;
Node(){};
Node(int i, int sz):subsz(sz), id(i){};
};
const int INF = 1e5;
vector<int> ids;
struct pSet{
vector<pii> events;
vector<Node> tree;
pSet(){
tree.reserve(500);
tree.push_back(create(-1, -1));
events.push_back({0, 0});
}
void set(int t, int id, int v){
events.push_back({t, update(id, v, 0, INF, events.back().second)});
}
vector<int> get_inside_at(int t){
int cur= 0;
for(int step = (1<<18); step>=1; step/=2){
if(cur+step<events.size()){
if(events[cur+step].first<=t){
cur+=step;
}
}
}
get(0, INF, events[cur].second);
vector<int> res;
swap(res, ids);
return res;
}
Node create(int lid, int rid){
Node res;
res.subsz = 0;
res.l = lid;
res.r = rid;
if(res.l!=-1){
res.subsz += tree[res.l].subsz;
}
if(res.r!=-1){
res.subsz += tree[res.r].subsz;
}
return res;
}
int update(int id, int v, int lt, int rt, int t){
Node res;
if(lt==rt){
res = Node(id, v);
}
else{
int mid = (lt+rt)/2;
int lid= -1, rid= -1;
if(t!=-1){
lid= tree[t].l;
rid =tree[t].r;
}
if(id<=mid){
res = create(update(id, v, lt, mid, lid), rid);
}
else{
res = create(lid, update(id, v, mid+1, rt, rid));
}
}
if(res.subsz>0|| (lt==0 && rt==INF)){
tree.push_back(res);
return tree.size()-1;
}
else{
return -1;
}
}
void get( int lt, int rt, int t){
if(lt==rt){
if(tree[t].subsz == 1){
ids.push_back(tree[t].id);
}
}
else{
int mid =(lt+rt)/2;
if(tree[t].l!=-1){
get(lt, mid, tree[t].l);
}
if(tree[t].r!=-1){
get(mid+1, rt, tree[t].r);
}
}
}
};
vector<pSet> vs;
vector<int> h;
set<pii> cur;
vector<int> redir;
vector<int> order;
int n;
void init(int N, int D, int H[]) {
vs.resize(N);
h.resize(N);
redir.resize(N);
order.resize(N);
for(int i = 0; i<N; i++){
h[i] = H[i];
order[i] = i;
}
auto cmp =[&](int a, int b){
return h[a]<h[b];
};
sort(order.begin(),order.end(), cmp);
sort(h.begin(), h.end());
n= N;
for(int i = 0; i<n; i++){
redir[order[i]] = i;
}
}
void curseChanges(int U, int A[], int B[]) {
for(int i = 0; i<U; i++){
int a= redir[A[i]], b= redir[B[i]];
if(a>b){
swap(a, b);
}
if((cur.find({a, b})!=cur.end())){
cur.erase({a, b});
vs[a].set(i+1, b, 0);
vs[b].set(i+1, a, 0);
}
else{
cur.insert({a, b});
vs[a].set(i+1, b, 1);
vs[b].set(i+1, a, 1);
}
}
}
int dist(vector<int>& a, vector<int>& b){
if(a.size() == 0 || b.size() == 0){
return 1e9;
}
int ia =0, ib = 0;
int res= abs(a[0]-b[0]);
while(ia<a.size()-1 || ib<b.size()-1){
if(ia==a.size()-1){
ib++;
}
else if(ib==b.size()-1){
ia++;
}
else if(a[ia]<=b[ib]){
ia++;
}
else{
ib++;
}
res = min(res, abs(a[ia]-b[ib]));
}
return res;
}
int question(int x, int y, int v) {
auto vx = vs[redir[x]].get_inside_at(v);
for(int& e: vx){
e = h[e];
}
auto vy = vs[redir[y]].get_inside_at(v);
for(int& e: vy){
e = h[e];
}
return dist(vx, vy);
}
int H[1000*1000];
int A[1000*1000];
int B[1000*1000];
signed main(){
int N, D, U, Q;
std::cin >> N >> D >> U >> Q;
for(int i = 0; i<N; i++){
cin>>H[i];
}
init(N, D, H);
for(int i = 0; i<U; i++){
cin>>A[i];
cin>>B[i];
}
curseChanges(U, A, B);
for(int i= 0; i<Q; i++){
int a, b, v;
cin>>a>>b>>v;
cout<<question(a, b, v)<<endl;
}
}