YEZAELP

CUBE-133: Xmas Beam

Dec 2nd, 2021
730
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int inf = 1e9;
  5. using pi = pair <int, int>;
  6.  
  7. bool Check(int check, int n, int h, pi ar[]){
  8.     deque <pi> mx;
  9.     deque <pi> mn;
  10.     for(int i=1;i<=n;i++){
  11.         while(!mn.empty() and ar[i].first - mn.front().first > check)
  12.             mn.pop_front();
  13.         while(!mx.empty() and ar[i].first - mx.front().first > check)
  14.             mx.pop_front();
  15.         while(!mn.empty() and mn.back().second >= ar[i].second)
  16.             mn.pop_back();
  17.         while(!mx.empty() and mx.back().second <= ar[i].second)
  18.             mx.pop_back();
  19.         mn.push_back(ar[i]);
  20.         mx.push_back(ar[i]);
  21.         if(abs(mx.front().second - mn.front().second) >= h) return true;
  22.     }
  23.     return false;
  24. }
  25.  
  26. void Solve(){
  27.     int n, h;
  28.     scanf("%d %d", &n, &h);
  29.  
  30.     pi ar[n + 1];
  31.     for(int i=1;i<=n;i++) scanf("%d %d", &ar[i].first, &ar[i].second);
  32.  
  33.     sort(ar + 1, ar + n + 1);
  34.  
  35.     int ans = inf, l = 0, r = inf;
  36.     while(l <= r){
  37.         int mid = (l + r) / 2;
  38.         if(Check(mid, n, h, ar)){
  39.             r = mid - 1;
  40.             ans = min(ans, mid);
  41.         }
  42.         else l = mid + 1;
  43.     }
  44.  
  45.     printf("%d\n", ans == inf ? -1 : ans);
  46. }
  47.  
  48. int main(){
  49.  
  50.     int Q;
  51.     scanf("%d", &Q);
  52.  
  53.     while(Q --)
  54.         Solve();
  55.  
  56.     return 0;
  57. }
RAW Paste Data