fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6. inline int power(int a, int b) {
  7.     int x = 1;
  8.     while (b) {
  9.         if (b & 1) x *= a;
  10.         a *= a;
  11.         b >>= 1;
  12.     }
  13.     return x;
  14. }
  15.  
  16.  
  17. const int M = 1000000007;
  18. const int N = 3e5+9;
  19. const int INF = 2e9+1;
  20. const int LINF = 2000000000000000001;
  21.  
  22. //_ ***************************** START Below *******************************
  23.  
  24.  
  25. int n, m, stLen, elLen, v, k;
  26. vector<int> stairs;
  27. vector<int> elevators;
  28.  
  29. void consistency(vector<vector<int>>& q){
  30.     sort(begin(elevators), end(elevators));
  31.     sort(begin(stairs), end(stairs));
  32.  
  33.     int stairDist = n-1;
  34.     int eleDist = (n+1+(v-1))/v;
  35.  
  36.     for(auto& it : q){
  37.         int sx = it[0];
  38.         int sy = it[1];
  39.         int dx = it[2];
  40.         int dy = it[3];
  41.  
  42.         int ans = LINF;
  43.  
  44.         // 1. Check direct walk if on the same floor (Standard edge case)
  45.         if(sx == dx) {
  46.             ans = abs(sy - dy);
  47.         }
  48.  
  49.         // 2. Check Elevators (closest two neighbors to sy)
  50.         auto e_it = upper_bound(begin(elevators), end(elevators), sy);
  51.  
  52.         // Option A: Elevator >= sy (Ceil)
  53.         if(e_it != end(elevators)){
  54.             int d = *e_it;
  55.             int cost = abs(d-sy) + abs(d-dy) + (abs(dx-sx)+v-1)/v;
  56.             ans = min(ans, cost);
  57.         }
  58.  
  59.         // Option B: Elevator < sy (Floor)
  60.         if(e_it != begin(elevators)){
  61.             int d = *prev(e_it);
  62.             int cost = abs(d-sy) + abs(d-dy) + (abs(dx-sx)+v-1)/v;
  63.             ans = min(ans, cost);
  64.         }
  65.  
  66.         // 3. Check Stairs (closest two neighbors to sy)
  67.         auto s_it = upper_bound(begin(stairs), end(stairs), sy);
  68.  
  69.         // Option A: Stair >= sy (Ceil)
  70.         if(s_it != end(stairs)){
  71.             int d = *s_it;
  72.             int cost = abs(d-sy) + abs(d-dy) + abs(dx-sx);
  73.             ans = min(ans, cost);
  74.         }
  75.  
  76.         // Option B: Stair < sy (Floor)
  77.         if(s_it != begin(stairs)){
  78.             int d = *prev(s_it);
  79.             int cost = abs(d-sy) + abs(d-dy) + abs(dx-sx);
  80.             ans = min(ans, cost);
  81.         }
  82.  
  83.         cout << ans << endl;
  84.     }
  85. }
  86.  
  87.  
  88.  
  89.  
  90. void solve() {
  91.  
  92.  
  93.     cin>>n >> m >> stLen >> elLen >> v;
  94.     stairs.resize(stLen);
  95.     elevators.resize(elLen);
  96.     for(int i=0; i<stLen; i++) cin >> stairs[i];
  97.     for(int i=0; i<elLen; i++) cin >> elevators[i];
  98.     cin >> k;
  99.     vector<vector<int>> q(k);
  100.     for(int i=0; i<k; i++){
  101.         int x, y, a, b;
  102.         cin >> x >> y >> a >> b;
  103.         q[i] = {x,y,a,b};
  104.     }
  105.     consistency(q);
  106.  
  107.  
  108. }
  109.  
  110.  
  111.  
  112.  
  113. int32_t main() {
  114.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  115.  
  116.     int t = 1;
  117.     cin >> t;
  118.     while (t--) {
  119.         solve();
  120.     }
  121.  
  122.     return 0;
  123. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
2
5 6 1 1 3
2
5
3
1 1 5 6
1 3 5 4
3 3 5 3
100 100 1 0 49
72

1
40 96 37 5
stdout
copy 
7
5
4
94
https://ideone.com/wgnmbf
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

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!