fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. using namespace std;
  6. //#define endl '\n'
  7. #define ll long long
  8. #define pi pair<int, int>
  9. #define f first
  10. #define s second
  11.  
  12. const int mxn = 100000;
  13. int n, m, k, q;
  14. int a[mxn];
  15. vector<vector<pi>> s[mxn];
  16. vector<int> v[2];
  17.  
  18. int id(int x, int y){
  19. 	for(int i = 0; i < s[x].size(); i++){
  20. 		if(s[x][i].back().s == y) return i;
  21. 	}
  22. 	return -1;
  23. }
  24.  
  25. void edg(int x, int y, int z){
  26. 	int it = id(x, y);
  27. 	if(~it) s[x][it].push_back({z, -1});
  28. 	else if(~(it = id(x, -1))) s[x][it].push_back({z, y});
  29. 	else s[x].push_back(vector<pi>(1, {z, y}));
  30. }
  31.  
  32. void qry(int x, int y, int z){
  33. 	v[z].clear();
  34. 	for(int i = 0; i < s[x].size() && s[x][i][0].f <= y; i++){
  35. 		int it = (--lower_bound(s[x][i].begin(), s[x][i].end(), (pi){y + 1, -1}))->s;
  36. 		if(~it) v[z].push_back(a[it]);
  37. 	}
  38. 	sort(v[z].begin(), v[z].end());
  39. }
  40.  
  41. int main(){
  42. 	ios::sync_with_stdio(0);
  43. 	cin.tie(0);
  44.  
  45. 	cin >> n >> k >> m >> q;
  46.  
  47. 	for(int i = 0; i < n; i++) cin >> a[i];
  48.  
  49. 	for(int i = 1; i <= m; i++){
  50. 		int u, v;
  51. 		cin >> u >> v;
  52. 		edg(u, v, i), edg(v, u, i);
  53. 	}
  54.  
  55. 	while(q--){
  56. 		int x, y, z;
  57. 		cin >> x >> y >> z;
  58.  
  59. 		qry(x, z, 0), qry(y, z, 1);
  60.  
  61. 		int ret = 1e9;
  62. 		for(int i = 0, j = 0; i < v[0].size() && j < v[1].size(); i++){
  63. 			while(j < v[1].size() - 1 && v[1][j + 1] < v[0][i]) j++;
  64. 			ret = min(ret, abs(v[0][i] - v[1][j]));
  65. 			if(j < v[1].size() - 1) ret = min(ret, abs(v[0][i] - v[1][j + 1]));
  66. 		}
  67.  
  68. 		cout << ret << endl;
  69. 	}
  70.  
  71. 	return 0;
  72. }
Success #stdin #stdout 0s 5948KB
comments (?)
stdin
copy 
6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4
3 0 8
0 5 5
3 0 11
stdout
copy 
26
0
1000000000
14
https://ideone.com/CUYhGq
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!