Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Manhattan Distance

dgc9715 Apr 6th, 2020 280 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.  
  5. #ifdef NeverBeRed
  6. #include "debug.h"
  7. #else
  8. #define debug(...) 9715
  9. #endif
  10. typedef long long ll;
  11. typedef long double ld;
  12. typedef complex<ld> point;
  13. #define F first
  14. #define S second
  15.  
  16. struct info
  17. {
  18.     int x, l, r;
  19. } que[100005];
  20.  
  21. struct fenwick
  22. {
  23.     int n;
  24.     int f[200005];
  25.  
  26.     inline int query(int p)
  27.     {
  28.         int ret = 0;
  29.         for (++p; p > 0; p -= p & -p)
  30.             ret += f[p];
  31.         return ret;
  32.     }
  33.  
  34.     inline void update(int p, int x)
  35.     {
  36.         for (++p; p <= n; p += p & -p)
  37.             f[p] += x;
  38.     }
  39. } L, R;
  40.  
  41. #define lwb1(x) (lower_bound(vals1, end1, x) - vals1)
  42. #define lwb2(x) (lower_bound(vals2, end2, x) - vals2)
  43.  
  44. int vals1[200005], vals2[200005];
  45. pair<int, int> a[100005];
  46.  
  47. int main()
  48. {
  49.     #ifdef TurnRed
  50.         freopen("a.in", "r", stdin);
  51.         //freopen("a.out", "w", stdout);
  52.     #endif
  53.  
  54.     ios_base::sync_with_stdio(0), cin.tie(0);
  55.  
  56.     int n; ll k;
  57.     cin >> n >> k;
  58.     for (int i = 0; i < n; ++i) cin >> a[i].F >> a[i].S;
  59.     sort(a, a+n);
  60.  
  61.     int lo = 1, hi = 4e8;
  62.     while (lo < hi)
  63.     {
  64.         int md = (lo + hi) >> 1;
  65.  
  66.         int p1 = 0, p2 = 0;
  67.         vals1[p1++] = a[n-1].S - md;
  68.         vals2[p2++] = a[n-1].S + md;
  69.         for (int i = n-2, sh = 0; i >= 0; --i)
  70.         {
  71.             sh += a[i+1].F - a[i].F;
  72.             vals1[p1++] = a[i].S - md - sh;
  73.             vals2[p2++] = a[i].S + md + sh;
  74.         }
  75.         sort(vals1, vals1+p1);
  76.         auto end1 = unique(vals1, vals1+p1);
  77.         sort(vals2, vals2+p2);
  78.         auto end2 = unique(vals2, vals2+p2);
  79.         L.n = ++p1;
  80.         R.n = ++p2;
  81.         memset(L.f, 0, sizeof(int)*p1);
  82.         memset(R.f, 0, sizeof(int)*p2);
  83.  
  84.         int pt = 0, fpt = 0;
  85.         int lwl = lwb1(a[n-1].S - md);
  86.         int lwr = lwb2(a[n-1].S + md);
  87.         L.update(lwl, +1);
  88.         R.update(lwr, +1);
  89.         que[pt++] = { md, lwl, lwr };
  90.  
  91.         ll ret = 0; int sh = 0;
  92.         for (int i = n-2; i >= 0; --i)
  93.         {
  94.             sh += a[i+1].F - a[i].F;
  95.             while (fpt != pt && que[fpt].x < sh)
  96.             {
  97.                 L.update(que[fpt].l, -1);
  98.                 R.update(que[fpt].r, -1);
  99.                 ++fpt;
  100.             }
  101.  
  102.             ret += L.query(lwb1(a[i].S - sh + 1)-1) - R.query(lwb2(a[i].S + sh)-1);
  103.             lwl = lwb1(a[i].S - md - sh);
  104.             lwr = lwb2(a[i].S + md + sh);
  105.             L.update(lwl, +1);
  106.             R.update(lwr, +1);
  107.             que[pt++] = { md + sh, lwl, lwr };
  108.         }
  109.  
  110.         if (ret < k)
  111.             lo = md + 1;
  112.         else
  113.             hi = md;
  114.     }
  115.     cout << lo << "\n";
  116.  
  117.     return 0;
  118. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top