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;
}
Compilation message (stderr)
potion.cpp: In function 'int id(int, int)':
potion.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i = 0; i < s[x].size(); i++){
| ~~^~~~~~~~~~~~~
potion.cpp: In function 'void qry(int, int, int)':
potion.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i = 0; i < s[x].size() && s[x][i][0].f <= y; i++){
| ~~^~~~~~~~~~~~~
potion.cpp: In function 'int main()':
potion.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i = 0, j = 0; i < v[0].size() && j < v[1].size(); i++){
| ~~^~~~~~~~~~~~~
potion.cpp:63:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i = 0, j = 0; i < v[0].size() && j < v[1].size(); i++){
| ~~^~~~~~~~~~~~~
potion.cpp:64:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | while(j < v[1].size() - 1 && v[1][j + 1] < v[0][i]) j++;
| ~~^~~~~~~~~~~~~~~~~
potion.cpp:66:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | if(j < v[1].size() - 1) ret = min(ret, abs(v[0][i] - v[1][j + 1]));
| ~~^~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cccZfEqe.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cchrCL6c.o:potion.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cccZfEqe.o: in function `main':
grader.cpp:(.text.startup+0xec): undefined reference to `init(int, int, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x184): undefined reference to `curseChanges(int, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x1d9): undefined reference to `question(int, int, int)'
collect2: error: ld returned 1 exit status