KalininN

GP of NorthBeach G

Nov 30th, 2020
184
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 LOCAL
  6.     #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  7. #else
  8.     #define eprintf(...) 42
  9. #endif
  10.  
  11. using ll = long long;
  12. using ld = long double;
  13. using D = double;
  14. using uint = unsigned int;
  15. template<typename T>
  16. using pair2 = pair<T, T>;
  17. using pii = pair<int, int>;
  18. using pli = pair<ll, int>;
  19. using pll = pair<ll, ll>;
  20. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  21.  
  22. #define pb push_back
  23. #define mp make_pair
  24. #define all(x) (x).begin(),(x).end()
  25. #define fi first
  26. #define se second
  27.  
  28. const int MX = 1e8 + 2;
  29. const int inf = 5 * MX;
  30.  
  31. const int POINT = 5;
  32. const int QUERY = 0;
  33. const int WALL = 1;
  34.  
  35. const int treesize = 1 << 28;
  36.  
  37. struct tnode
  38. {
  39.     tnode *l, *r;
  40.     int minv;
  41.     int push;
  42.    
  43.     tnode (int t)
  44.     {
  45.         l = NULL;
  46.         r = NULL;
  47.         minv = t;
  48.         push = inf;
  49.     }
  50. };
  51.  
  52. using pnode = tnode*;
  53.  
  54. struct tev
  55. {
  56.     int x, t, y1, y2;
  57. };
  58.  
  59. const int maxn = 200005;
  60.  
  61. vector<tev> evs;
  62. multiset<int> bany;
  63. int x[maxn], y[maxn], answer[maxn];
  64. int n, nq;
  65.  
  66. int getmin(pnode cur)
  67. {
  68.     return cur == NULL ? inf : cur->minv;
  69. }
  70.  
  71. pnode put(pnode cur, int cl, int cr, int l, int r, int t)
  72. {
  73.     if (cl > r || cr < l) return cur;
  74.     if (cur == NULL) cur = new tnode(inf);
  75.     if (cl >= l && cr <= r)
  76.     {
  77.         cur->push = min(cur->push, t);
  78.         cur->minv = min(cur->minv, t);
  79.         return cur;
  80.     }
  81.     int cm = (cl + cr) / 2;
  82.     cur->l = put(cur->l, cl, cm, l, r, t);
  83.     cur->r = put(cur->r, cm + 1, cr, l, r, t);
  84.     cur->minv = min(cur->push, min(getmin(cur->l), getmin(cur->r)));
  85.     return cur;
  86. }
  87.  
  88. int get(pnode cur, int cl, int cr, int l, int x, int y, int push)
  89. {
  90.     if (cr < l) return inf;
  91.     int ycheck = max(y, cl);
  92.     int ans = max(ycheck - y, push - x);
  93.     if (cur == NULL) return ans;
  94.     if (cl >= l && min(push, cur->minv) >= x + (cr - y + 1)) return min(push, cur->minv) - x;
  95.     int cm = (cl + cr) / 2;
  96.     ans = min(ans, get(cur->l, cl, cm, l, x, y, min(push, cur->push)));
  97.     if (ans >= (cm + 1) - y) ans = min(ans, get(cur->r, cm + 1, cr, l, x, y, min(push, cur->push)));
  98.     return ans;
  99. }
  100.  
  101. void solve()
  102. {
  103.     pnode root = new tnode(inf);
  104.     evs.clear();
  105.     bany.clear();
  106.     for (int i =0 ; i < n; i++)
  107.     {
  108.         scanf("%d%d", &x[i], &y[i]);
  109.         x[i] += MX;
  110.         y[i] += MX;
  111.     }
  112.     x[n] = x[0];
  113.     y[n] = y[0];
  114.     for (int i = 0; i < n; i++)
  115.     {
  116.         if (x[i] == x[i + 1]) evs.pb({x[i], WALL, min(y[i], y[i + 1]), max(y[i], y[i + 1])});
  117.         else
  118.         {
  119.             evs.pb({max(x[i], x[i + 1]), +POINT, y[i], -1});
  120.             evs.pb({min(x[i], x[i + 1]), -POINT, y[i], -1});
  121.         }
  122.     }
  123.     for (int q = 0; q < nq; q++)
  124.     {
  125.         int x, y;
  126.         scanf("%d%d", &x, &y);
  127.         x += MX;
  128.         y += MX;
  129.         evs.pb({x, QUERY, y, q});
  130.     }
  131.     sort(all(evs), [](const tev &a, const tev &b)
  132.     {
  133.         if (a.x != b.x) return a.x > b.x;
  134.         return a.t < b.t;
  135.     });
  136.     bany.insert(inf);
  137.     for (auto ev : evs)
  138.     {
  139.         if (ev.t == WALL)
  140.         {
  141.             put(root, 0, treesize - 1, ev.y1, ev.y2 - 1, ev.x);
  142.         } else if (ev.t == +POINT)
  143.         {
  144.             bany.insert(ev.y1);
  145.         } else if (ev.t == -POINT)
  146.         {
  147.             bany.erase(bany.find(ev.y1));
  148.         } else
  149.         {
  150.             int ans = get(root, 0, treesize - 1, ev.y1, ev.x, ev.y1, inf);
  151.             ans = min(ans, *bany.upper_bound(ev.y1) - ev.y1);
  152.             answer[ev.y2] = ans;
  153.         }
  154.     }
  155.     for (int i = 0; i < nq; i++) printf("%d\n", answer[i]);
  156. }
  157.  
  158. int main()
  159. {
  160.     while (scanf("%d%d", &n, &nq) == 2) solve();
  161.     return 0;
  162. }
  163.  
RAW Paste Data