fork download
copy 
  1. //Billions of bilious blue blistering barnacles in a thundering typhoon!
  2. //Yesterday is history, tomorrow is a mystery, today is a gift of God, which is why we call it the present.
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. using ll = long long;
  6. const ll MX = (ll) 2e18;
  7. void solve(){
  8.     int n, m;
  9.     cin >> n >> m;
  10.     vector<tuple<ll, ll, bool>> a;
  11.     vector<ll> y;
  12.     for(int i = 1; i <= n; i++){
  13.         ll o, p;
  14.         cin >> o >> p;
  15.         y.push_back(p);
  16.         a.push_back({o, p, 0});
  17.     }
  18.     for(int i = 1; i <= m; i++){
  19.         ll o, p;
  20.         cin >> o >> p;
  21.         y.push_back(p);
  22.         a.push_back({o, p, 1});
  23.     }
  24.     sort(a.begin(), a.end());
  25.     sort(y.begin(), y.end());
  26.     y.resize(unique(y.begin(), y.end()) - y.begin());
  27.     map<ll, int> mp;
  28.     int k = 0;
  29.     for(ll j: y){
  30.         mp[j] = ++k;
  31.     } 
  32.     vector<vector<ll>> pref_min(2, vector<ll>(k + 1, MX)), suf_min(2, vector<ll>(k + 1, MX));
  33.     function<void(int, ll, bool)> update_pref = [&](int i, ll val, bool t){
  34.         while(i <= k){
  35.             pref_min[t][i] = min(pref_min[t][i], val);
  36.             i += i & -i;
  37.         }
  38.     };
  39.     function<ll(int, bool)> query_pref = [&](int i, bool t){
  40.         ll ret = MX;
  41.         while(i){
  42.             ret = min(ret, pref_min[t][i]);
  43.             i -= i & -i;
  44.         }
  45.         return ret;
  46.     };
  47.     function<void(int, ll, bool)> update_suf = [&](int i, ll val, bool t){
  48.         while(i){
  49.             suf_min[t][i] = min(suf_min[t][i], val);
  50.             i -= i & -i;
  51.         }
  52.     };
  53.     function<ll(int, bool)> query_suf = [&](int i, bool t){
  54.         ll ret = MX;
  55.         while(i <= k){
  56.             ret = min(ret, suf_min[t][i]);
  57.             i += i & -i;
  58.         }
  59.         return ret;
  60.     };
  61.     ll ans = MX;
  62.     for(auto [x, y, i]: a){
  63.         ans = min({ans, x + y + query_pref(mp[y], !i), x - y + query_suf(mp[y], !i)});
  64.         update_pref(mp[y], - x - y, i);
  65.         update_suf(mp[y], - x + y, i);
  66.     }
  67.     assert(ans >=  0 && ans <= MX);
  68.     cout << ans << "\n";
  69. }
  70. int main(){
  71.     ios::sync_with_stdio(0), cin.tie(0);
  72.     int tt = 1;
  73.     cin >> tt;
  74.     while(tt--){
  75.         solve();
  76.     }
  77. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2000000000000000000
https://ideone.com/FOEv8W
language:
C++ (gcc 8.3)
created:
3 days 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!