Submission #1149624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149624		Perl32	Road Construction (JOI21_road_construction)	C++20	32 / 100	10089 ms	127492 KiB

road_construction

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template<typename T> using normal_queue = priority_queue<T, vector<T>, greater<T>>;

template<typename T>
struct WT {
   vector<vector<T>> t, pref;
   vector<T> srt;
   int sz;

   WT(vector<T>& a) {
      srt = a;
      sort(srt.begin(), srt.end());
      srt.resize(unique(srt.begin(), srt.end()) - srt.begin());
      sz = 1;
      while (sz < (int) srt.size()) sz <<= 1;
      t.resize(sz << 1);
      pref.resize(sz << 1);
      t[1] = a;
      for (auto& x : t[1]) x = lower_bound(srt.begin(), srt.end(), x) - srt.begin();
      build(1, 0, srt.size());
   }

   void build(int x, int lx, int rx) {
      if (lx + 1 == rx) return;
      int m = (lx + rx) >> 1;
      pref[x].resize(t[x].size() + 1);
      for (int i = 0; i < (int) t[x].size(); ++i) {
         bool le = (t[x][i] < m);
         pref[x][i + 1] = pref[x][i] + le;
         if (le) {
            t[x << 1].push_back(t[x][i]);
         } else {
            t[x << 1 | 1].push_back(t[x][i]);
         }
      }
      build(x << 1, lx, m);
      build(x << 1 | 1, m, rx);
   }

   int le(int l, int r, int v, int x, int lx, int rx) {
      if (lx >= v) return 0;
      if (rx <= v) return r - l;
      int m = (lx + rx) >> 1, lb = pref[x][l], rb = pref[x][r];
      return le(lb, rb, v, x << 1, lx, m) + le(l - lb, r - rb, v, x << 1 | 1, m, rx);
   }

   int le(int l, int r, T v) { // counting elements lower than v in [l, r)
      v = lower_bound(srt.begin(), srt.end(), v) - srt.begin();
      return le(l, r, v, 1, 0, srt.size());
   }

   int kth(int l, int r, int k, int x, int lx, int rx) {
      if (lx + 1 == rx) {
         return lx;
      }
      int m = (lx + rx) >> 1, lb = pref[x][l], rb = pref[x][r], flex = rb - lb;
      if (flex >= k) return kth(lb, rb, k, x << 1, lx, m);
      return kth(l - lb, r - rb, k - flex, x << 1 | 1, m, rx);
   }

   T kth(int l, int r, int k) { // finding kth element in [l, r)
      return srt[kth(l, r, k, 1, 0, srt.size())];
   }

   int eq(int l, int r, int v, int x, int lx, int rx) { // number of occurance of x in [l, r)
      if (lx + 1 == rx) return r - l;
      int m = (lx + rx) >> 1, lb = pref[x][l], rb = pref[x][r];
      if (v < m) return eq(lb, rb, v, x << 1, lx, m);
      return eq(l - lb, r - rb, v, x << 1 | 1, m, rx);
   }

   int eq(int l, int r, T v) {
      return eq(l, r, v, 1, 0, srt.size());
   }
};

const ll inf = 5e9;

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, k;
    cin >> n >> k;
    vector<pair<ll, ll>> a(n);
    ll mnX = inf, mxX = -inf, mnY = inf, mxY = -inf;
    for (auto& c : a) {
        ll x, y;
        cin >> x >> y;
        c = {x + y, x - y};
        mnX = min(mnX, c.first);
        mxX = max(mxX, c.first);
        mnY = min(mnY, c.second);
        mxY = max(mxY, c.second);
    }
    sort(a.begin(), a.end());
    vector<ll> y(n);
    for (int i = 0; i < n; ++i) y[i] = a[i].second;
    WT<ll> tt(y);
    auto counting = [&](int i, ll m) {
        ll rx = a[i].first + m, ly = a[i].second - m, ry = a[i].second + m;
        rx = upper_bound(a.begin(), a.end(), pair{rx, inf}) - a.begin();
        return tt.le(i, rx, ry + 1) - tt.le(i, rx, ly);
    };
    ll bord = max(mxX - mnX, mxY - mnY);
    vector<ll> cnt(n, 1);
    auto solve = [&](ll i) {
        ll lx = -1, rx = bord + 1;
        while (lx + 1 < rx) {
            ll m = (lx + rx) >> 1;
            if (counting(i, m) <= cnt[i]) {
                lx = m;
            } else {
                rx = m;
            }
        }
        return rx;
    };
    normal_queue<pair<ll, ll>> pq;
    for (ll i = 0; i < n - 1; ++i) pq.emplace(solve(i), i);
    while (k--) {
        auto [d, j] = pq.top(); pq.pop();
        cnt[j]++;
        cout << d << '\n';
        if (cnt[j] != n - j) pq.emplace(solve(j), j);
    }
}

/*

 */

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35