| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1301762 | kerem | The Potion of Great Power (CEOI20_potion) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("-fipa-sra,-fgcse-lm,-fgcse,inline,unroll-all-loops,no-stack-protector,O3,fast-math,Ofast")
#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
#define pb push_back
#define emb emplace_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 1000
#define inf 1e9
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
struct Node{
int l,r;
Node(){l=r=0;}
Node(int ll,int rr){l=ll;r=rr;}
};
int sz=0;
vector<Node> tree;
vector<vector<int>> t,v;
vector<int> h,ind;
vector<ii> trust;
int newNode(int l=0,int r=0){
tree.emb(l,r);
return sz++;
}
inline int update(int node,int l,int r,int qx){
if(l==r){
if(node) return 0;
node=newNode();
return node;
}
int mid=(l+r)/2;
if(qx<=mid){
int newL=update(tree[node].l,l,mid,qx);
if(!newL && !tree[node].r) return 0;
else return newNode(newL,tree[node].r);
}
else{
int newR=update(tree[node].r,mid+1,r,qx);
if(!tree[node].l && !newR) return 0;
else return newNode(tree[node].l,newR);
}
}
inline void query(int node1,int node2,int l,int r){
if(!node1 && !node2) return;
if(l==r){
if(node1) trust.pb({h[l],1});
if(node2) trust.pb({h[l],2});
return;
}
int mid=(l+r)/2;
query(tree[node1].l,tree[node2].l,l,mid);
query(tree[node1].r,tree[node2].r,mid+1,r);
}
void solve(){
newNode();
int n,D,m,q;
cin >> n >> D >> m >> q;
vector<ii> zort;
h.assign(n,0);ind.assign(n,0);
for(int i=0;i<n;i++){
cin >> h[i];
zort.emb(h[i],i);
}
sort(all(h));
sort(all(zort));
for(int i=0;i<n;i++)
ind[zort[i].sc]=i;
t.assign(n,vector<int>(1,0));
v.assign(n,vector<int>(1,0));
for(int i=1;i<=m;i++){
int x,y;cin >> x >> y;
x=ind[x];y=ind[y];
t[x].pb(i);t[y].pb(i);
v[x].pb(update(v[x].back(),0,n-1,y));
v[y].pb(update(v[y].back(),0,n-1,x));
}
while(q--){
int x,y,T;
cin >> x >> y >> T;
x=ind[x];y=ind[y];
int itl=upper_bound(all(t[x]),T)-t[x].begin()-1;
int itr=upper_bound(all(t[y]),T)-t[y].begin()-1;
trust.clear();
query(v[x][itl],v[y][itr],0,n-1);
int ans=inf;
for(int i=1;i<(int)trust.size();i++){
if(trust[i].sc!=trust[i-1].sc)
ans=min(ans,trust[i].fr-trust[i-1].fr);
}
cout << ans << endl;
}
}
int32_t main(){
cout << fixed << setprecision(0);
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int test=1;
//~ cin >> test;
while(test--){
solve();
}
}