Submission #1149614

#TimeUsernameProblemLanguageResultExecution timeMemory
1149614Perl32Road Construction (JOI21_road_construction)C++17
59 / 100
10091 ms127488 KiB
//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 = 0x3f3f3f3f3f3f; 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); for (auto& c : a) { ll x, y; cin >> x >> y; c = {x + y, x - y}; } 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); }; vector<ll> cnt(n, 1); auto solve = [&](ll i) { ll lx = -1, rx = inf; 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); } } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...