Advertisement
KiK0S

Untitled

Feb 24th, 2019
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.61 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <set>
  6. #include <map>
  7. #include <queue>
  8. #include <fstream>
  9. #include <ctime>
  10. #include <random>
  11. #include <iomanip>
  12. #include <bitset>
  13.  
  14. using namespace std;
  15.  
  16. typedef long long ll;
  17.  
  18. #ifdef DEBUG
  19.     const int MAXN = 200;
  20. #else
  21.     const int MAXN = 1e6 + 200;
  22.     #define cerr if (false) cerr
  23. #endif
  24.  
  25. ll INF = 3e18;
  26. int MOD = 1e9 + 7;
  27. int n, m;
  28.  
  29. struct V {
  30.     ll x, y, z;
  31. };
  32.  
  33. V st[MAXN];
  34. V points[MAXN];
  35.  
  36. ll t[MAXN];
  37.  
  38. int SZ;
  39.  
  40. ll get(int pos) {
  41.     ll ans = -INF;
  42.     for (int i = pos + 1; i > 0; i -= i & -i) {
  43.         ans = max(ans, t[i]);
  44.     }
  45.     return ans;
  46. }
  47.  
  48. void upd(int pos, ll x) {
  49.     for (int i = pos + 1; i <= SZ; i += i & -i) {
  50.         t[i] = max(t[i], x);
  51.     }
  52. }
  53.  
  54. int id_y_a[MAXN];
  55. int id_y_b[MAXN];
  56. pair<ll, int> y_a[MAXN];
  57. pair<ll, int> y_b[MAXN];
  58.  
  59. bool check(ll mid) {
  60.     int ptr = 0;
  61.     int pnt_y = 0;
  62.     for (int i = 0; i < n; i++) {
  63.         while (ptr < m && y_a[ptr].first - mid > y_b[i].first) {
  64.             id_y_a[y_a[ptr++].second] = pnt_y++;
  65.         }
  66.         id_y_b[y_b[i].second] = pnt_y++;
  67.     }
  68.     while (ptr < m) {
  69.         id_y_a[y_a[ptr++].second] = pnt_y++;
  70.     }
  71.     SZ = pnt_y + 100;
  72.     for (int i = 0; i <= SZ; i++) {
  73.         t[i] = -INF;
  74.     }
  75.     int pnt = 0;
  76.     for (int i = 0; i < m; i++) {
  77.         while (pnt < n && st[pnt].x >= points[i].x - mid) {
  78.             upd(id_y_b[pnt], st[pnt].z);
  79.             pnt++;
  80.         }
  81.         ll bst = get(id_y_a[i]);
  82.         if (bst < points[i].z - mid) {
  83.             return 0;
  84.         }
  85.     }
  86.     return 1;
  87. }
  88.  
  89. void init() {
  90. }
  91.  
  92. void solve() {
  93.     init();
  94.     for (int j = 0; j < m; j++) {
  95.         cin >> points[j].x >> points[j].y >> points[j].z;
  96.     }
  97.     sort(points, points + m, [](V a, V b){
  98.         return a.x > b.x;
  99.     });
  100.     for (int j = 0; j < m; j++) {
  101.         y_a[j] = make_pair(points[j].y, j);
  102.     }
  103.     sort(y_a, y_a + m, [](pair<ll, int> a, pair<ll, int> b){
  104.         return a.first > b.first;
  105.     });
  106.     for (int i = 0; i < n; i++) {
  107.         cin >> st[i].x >> st[i].y >> st[i].z;
  108.     }
  109.     sort(st, st + n, [](V a, V b){
  110.         return a.x > b.x;
  111.     });
  112.     for (int i = 0; i < n; i++) {
  113.         y_b[i] = make_pair(st[i].y, i);
  114.     }
  115.     sort(y_b, y_b + n, [](pair<ll, int> a, pair<ll, int> b){
  116.         return a.first > b.first;
  117.     });
  118.     ll l = -INF;
  119.     ll r = INF;
  120.     while (l + 1 < r) {
  121.         ll mid = (l + r) >> 1;
  122.         if (check(mid)) {
  123.             r = mid;
  124.         }
  125.         else {
  126.             l = mid;
  127.         }
  128.     }
  129.     cout << r << '\n';
  130. }
  131.  
  132. signed main() {
  133.     #ifdef DEBUG
  134.         freopen("D.in", "r", stdin);
  135.         freopen("D.out", "w", stdout);
  136.     #else
  137.    
  138.     #endif
  139.     ios_base::sync_with_stdio(0);
  140.     cin.tie(0);
  141.     cout.tie(0);
  142.     while (cin >> m >> n) {
  143.         solve();
  144.     }
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement