Dang_Quan_10_Tin

Code em ạ

May 12th, 2021
514
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. using ll = long long;
  5. using ld = long double;
  6. using ull = unsigned long long;
  7.  
  8. constexpr bool typetest = 0;
  9. constexpr int N = 1e5 + 5;
  10. const int Inf = 1e9 + 7;
  11.  
  12. struct TData
  13. {
  14.     int c, l, r;
  15.     TData(const int &c = Inf, const int &l = 0, const int &r = 0) : c(c), l(l), r(r) {}
  16.     bool operator<(const TData &a) const
  17.     {
  18.         return c < a.c || (a.c == c && (l < a.l || (l == a.l && r < a.r)));
  19.     }
  20. };
  21.  
  22. struct SegmentTree
  23. {
  24.     vector<int> a, lazy;
  25.     vector<TData> st;
  26.  
  27.     void Build(int id, int l, int r)
  28.     {
  29.         if (l == r)
  30.         {
  31.             st[id] = TData(0, a[l - 1], a[l - 1]);
  32.             return;
  33.         }
  34.         Build(id << 1, l, (l + r) / 2);
  35.         Build(id << 1 | 1, (l + r) / 2 + 1, r);
  36.  
  37.         st[id] = Combine(st[id << 1], st[id << 1 | 1]);
  38.     }
  39.  
  40.     void Assign()
  41.     {
  42.         sort(a.begin(), a.end());
  43.         a.resize(unique(a.begin(), a.end()) - a.begin());
  44.  
  45.         lazy.assign(a.size() * 4, 0);
  46.         st.assign(a.size() * 4, Inf);
  47.         Build(1, 1, a.size());
  48.     }
  49.  
  50.     void Push(int id)
  51.     {
  52.         if (lazy[id])
  53.         {
  54.             lazy[id << 1] += lazy[id];
  55.             st[id << 1].c += lazy[id];
  56.             lazy[id << 1 | 1] += lazy[id];
  57.             st[id << 1 | 1].c += lazy[id];
  58.  
  59.             lazy[id] = 0;
  60.         }
  61.     }
  62.  
  63.     inline TData Combine(const TData &a, const TData &b)
  64.     {
  65.         TData x;
  66.         if (a.c < b.c)
  67.             x = a;
  68.         else if (b.c < a.c)
  69.             x = b;
  70.         else
  71.         {
  72.             x.c = a.c;
  73.             x.l = min(a.l, b.l);
  74.             x.r = max(b.l, b.r);
  75.         }
  76.  
  77.         return x;
  78.     }
  79.  
  80.     TData Update(int id, int l, int r, const int &x, const int &y, const int &v)
  81.     {
  82.         if (a[l - 1] > y || a[r - 1] < x)
  83.             return TData(Inf, 0, 0);
  84.         if (a[l - 1] >= x && a[r - 1] <= y)
  85.         {
  86.             lazy[id] += v;
  87.             st[id].c += v;
  88.             return st[id];
  89.         }
  90.  
  91.         Push(id);
  92.         TData z = Combine(Update(id << 1, l, (l + r) / 2, x, y, v), Update(id << 1 | 1, (l + r) / 2 + 1, r, x, y, v));
  93.         st[id] = Combine(st[id << 1], st[id << 1 | 1]);
  94.  
  95.         return z;
  96.     }
  97.  
  98.     TData Update(int l, int r, int v)
  99.     {
  100.         return Update(1, 1, a.size(), l, r, v);
  101.     }
  102.  
  103. } f[N], g;
  104.  
  105. vector<TData> in[N * 5], out[N * 5];
  106.  
  107. int n, k, x[N], y[N], c[N];
  108.  
  109. void Read()
  110. {
  111.     cin >> n >> k;
  112.  
  113.     for (int i = 1; i <= n; ++i)
  114.     {
  115.         cin >> x[i] >> y[i] >> c[i];
  116.         x[i] *= 2;
  117.         y[i] *= 2;
  118.     }
  119. }
  120.  
  121. bool Calculate()
  122. {
  123.     for (int i = 1; i <= 5e5; ++i)
  124.     {
  125.         for (auto j : in[i])
  126.         {
  127.             TData s = f[j.c].Update(j.l, j.r, 1);
  128.             if (s.c == 1)
  129.                 g.Update(s.l, s.r, -1);
  130.         }
  131.  
  132.         if (g.st[1].c <= -k)
  133.             return true;
  134.  
  135.         for (auto j : out[i])
  136.         {
  137.             TData s = f[j.c].Update(j.l, j.r, -1);
  138.             if (s.c == 0)
  139.                 g.Update(s.l, s.r, 1);
  140.         }
  141.     }
  142.  
  143.     return false;
  144. }
  145.  
  146. bool Check(int v)
  147. {
  148.     g.st.assign(g.a.size() * 4, Inf);
  149.     g.lazy.assign(g.a.size() * 4, 0);
  150.     g.Build(1, 1, g.a.size());
  151.  
  152.     for (int i = 1; i <= n; ++i)
  153.     {
  154.         in[max(1, x[i] - v)].emplace_back(c[i], y[i] - v, y[i] + v);
  155.  
  156.         if (y[i] - v > 1)
  157.             f[c[i]].a.emplace_back(y[i] - v - 1);
  158.         if (y[i] + v + 1 <= 5e5)
  159.             f[c[i]].a.emplace_back(y[i] + v + 1);
  160.         f[c[i]].a.emplace_back(max(1, y[i] - v));
  161.         f[c[i]].a.emplace_back(min((int)5e5, y[i] + v));
  162.  
  163.         if (x[i] + v <= 5e5)
  164.             out[x[i] + v].emplace_back(c[i], y[i] - v, y[i] + v);
  165.     }
  166.  
  167.     for (int i = 1; i <= k; ++i)
  168.         f[i].Assign();
  169.  
  170.     bool ok = Calculate();
  171.  
  172.     for (int i = 1; i <= 5e5; ++i)
  173.     {
  174.         in[i].clear();
  175.         out[i].clear();
  176.         if (i <= k)
  177.             f[i].a.clear(), f[i].st.clear(), f[i].lazy.clear();
  178.     }
  179.  
  180.     return ok;
  181. }
  182.  
  183. void Solve()
  184. {
  185.     g.a.resize((int)5e5);
  186.  
  187.     for (int i = 0; i < (int)g.a.size(); ++i)
  188.         g.a[i] = i + 1;
  189.  
  190.     int l = 0, m, h = 2.5e5;
  191.     while (l <= h)
  192.     {
  193.         m = (l + h) / 2;
  194.  
  195.         if (Check(m))
  196.             h = m - 1;
  197.         else
  198.             l = m + 1;
  199.     }
  200.  
  201.     cout << l;
  202. }
  203.  
  204. int32_t main()
  205. {
  206.     ios::sync_with_stdio(0);
  207.     cin.tie(0);
  208.     cout.tie(0);
  209.     int t(1);
  210.     if (typetest)
  211.         cin >> t;
  212.     for (int _ = 1; _ <= t; ++_)
  213.     {
  214.         Read();
  215.         Solve();
  216.     }
  217. }
RAW Paste Data