| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1022488 | hqminhuwu | 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.
//https://ideone.com/CUYhGq
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
//#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
const int mxn = 100000;
int n, m, k, q;
int a[mxn];
vector<vector<pi>> s[mxn];
vector<int> v[2];
int id(int x, int y){
for(int i = 0; i < s[x].size(); i++){
if(s[x][i].back().s == y) return i;
}
return -1;
}
void edg(int x, int y, int z){
int it = id(x, y);
if(~it) s[x][it].push_back({z, -1});
else if(~(it = id(x, -1))) s[x][it].push_back({z, y});
else s[x].push_back(vector<pi>(1, {z, y}));
}
void qry(int x, int y, int z){
v[z].clear();
for(int i = 0; i < s[x].size() && s[x][i][0].f <= y; i++){
int it = (--lower_bound(s[x][i].begin(), s[x][i].end(), (pi){y + 1, -1}))->s;
if(~it) v[z].push_back(a[it]);
}
sort(v[z].begin(), v[z].end());
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k >> m >> q;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
edg(u, v, i), edg(v, u, i);
}
while(q--){
int x, y, z;
cin >> x >> y >> z;
qry(x, z, 0), qry(y, z, 1);
int ret = 1e9;
for(int i = 0, j = 0; i < v[0].size() && j < v[1].size(); i++){
while(j < v[1].size() - 1 && v[1][j + 1] < v[0][i]) j++;
ret = min(ret, abs(v[0][i] - v[1][j]));
if(j < v[1].size() - 1) ret = min(ret, abs(v[0][i] - v[1][j + 1]));
}
cout << ret << endl;
}
return 0;
}