| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 317313 | soroush | The Potion of Great Power (CEOI20_potion) | C++14 | 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.
/*
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
//*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int ,int > pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn = 1e5 + 10;
const ll mod =1e9+7;
const ld PI = acos((ld)-1);
#define pb push_back
//#define endl '\n'
#define dokme(x) cout << x , exit(0);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ms(x , y) memset(x , y , sizeof x);
#define file_init freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
int n , d, u , q;
int h[maxn];
vector < pii > query[maxn] , ans;
vector < int > adr[maxn];
vector < int > vec[2];
vector < int > adj[4*maxn];
int bz = 64;
bool mark[maxn];
set < int > st;
vector < int > fuck;
int cur = 0;
void build(int v){
st.clear();
int cnt = 0;
for(int i = 0 ; i < int(query[v].size()) ; i ++){
cnt++;
mark[query[v][i].second] ^= 1;
if(!mark[query[v][i].second])st.erase(query[v][i].second);
else st.insert(query[v][i].second);
if(cnt==bz){
adr[v].pb(cur);
adj[cur].resize(st.size());
int i = 0;
for(int x : st) adj[cur][i++] = x;
cur++;
cnt = 0;
}
else
adr[v].pb(-1);
}
for(int i : st)mark[i] = 0;
}
int solve(){
sort(vec[0].begin() , vec[0].end());
sort(vec[1].begin() , vec[1].end());
int mn = 1e9;
int p1 = 0 , p2 = 0;
while(p1 < vec[0].size() and p2 < vec[1].size()){
mn = min(mn , abs(vec[0][p1] - vec[1][p2]));
if(vec[0][p1] < vec[1][p2])
p1 ++;
else
p2 ++;
}
return(mn);
}
void get(int v , int t , int ind = 0){
vec[ind].clear();
if(query[v].size() == 0) return;
if(query[v][0].first > t) return;
int l = 0 , r = query[v].size();
while(r - l > 1){
int mid = (l + r)/2;
if(query[v][mid].first > t)
r = mid;
else
l = mid;
}
fuck.clear();
while(l >= 0 and adr[v][l] == -1){
mark[query[v][l].second] ^= 1;
fuck.pb(query[v][l].second);
l --;
}
if(l >= 0 and adr[v][l] > -1){
for(int i : adj[adr[v][l]]){
mark[i] ^= 1;
fuck.pb(i);
}
}
for(int i : fuck)
if(mark[i]) vec[ind].pb(h[i]) , mark[i] = 0;
}
int32_t main(){
migmig
cin >> n >> d >> u >> q;
for(int i = 1 ; i <= n ; i ++)
cin >> h[i];
for(int i = 1 ; i <= u ; i ++){
int a ,b;
cin >> a >> b;
a ++ , b ++ ;
query[a].pb({i , b});
query[b].pb({i , a});
}
for(int i = 1 ; i <= n ; i ++)
build(i);
while(q --){
int x , y , v;
cin >> x >> y >> v;
x ++ , y ++ ;
get(x , v);
get(y , v , 1);
cout << solve() << endl;
}
return(0);
}