Submission #1049605

#TimeUsernameProblemLanguageResultExecution timeMemory
1049605ymmRoad Construction (JOI21_road_construction)C++17
38 / 100
10065 ms134932 KiB
#include <bits/stdc++.h> #define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x) #define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x) typedef long long ll; typedef std::pair<int, int> pii; typedef std::pair<ll , ll > pll; using namespace std; struct Seg { vector<vector<pll>> ys; int n; static bool cmp(const pll &a, const pll &b) { return a.second < b.second; } void init(const pll *&ptr, const pll *end, int i, int b, int e) { if (e - b == 1) { ys[i].clear(); while (ptr != end && ptr->first == b) ys[i].push_back(*ptr++); return; } init(ptr, end, 2*i+1, b, (b+e)/2); init(ptr, end, 2*i+2, (b+e)/2, e); ys[i].resize(ys[2*i+1].size() + ys[2*i+2].size()); merge(ys[2*i+1].begin(), ys[2*i+1].end(), ys[2*i+2].begin(), ys[2*i+2].end(), ys[i].begin(), cmp); } void init(int n, vector<pll> vals) { this->n = n; ys.resize(n*4); sort(vals.begin(), vals.end()); const pll *ptr = vals.data(); init(ptr, ptr + vals.size(), 0, 0, n); } typedef decltype(ys[0].begin()) iter; template<class Fn> void range_query(Fn fn, int l, int r, ll l2, ll r2, int i, int b, int e) { if (l <= b && e <= r) { iter it1 = lower_bound(ys[i].begin(), ys[i].end(), pll{INT_MIN, l2}, cmp); iter it2 = lower_bound(ys[i].begin(), ys[i].end(), pll{INT_MIN, r2}, cmp); return fn(it1, it2); } if (r <= b || e <= l) return; range_query(fn, l, r, l2, r2, 2*i+1, b, (b+e)/2); range_query(fn, l, r, l2, r2, 2*i+2, (b+e)/2, e); } ll count(int l, int r, ll l2, ll r2) { ll ans = 0; range_query([&](iter it1, iter it2) { ans += it2 - it1; }, l, r, l2, r2, 0, 0, n); return ans; } vector<pll> list(int l, int r, ll l2, ll r2) { vector<pll> ans; range_query([&](iter it1, iter it2) { ans.insert(ans.end(), it1, it2); }, l, r, l2, r2, 0, 0, n); return ans; } }; struct CompSeg { Seg seg; vector<ll> xs; int comp(ll x) { return lower_bound(xs.begin(), xs.end(), x) - xs.begin(); } void init(vector<pll> vals) { for (auto [x, _] : vals) xs.push_back(x); sort(xs.begin(), xs.end()); xs.resize(unique(xs.begin(), xs.end()) - xs.begin()); vector<pll> cmped; for (auto [x, y] : vals) cmped.emplace_back(comp(x), y); seg.init(xs.size(), cmped); } ll count(ll l, ll r, ll l2, ll r2) { return seg.count(comp(l), comp(r), l2, r2); } vector<pll> list(ll l, ll r, ll l2, ll r2) { auto vec = seg.list(comp(l), comp(r), l2, r2); for (auto &[x, y] : vec) x = xs[x]; return vec; } }; struct SquareSeg { CompSeg seg; vector<pll> vals; static pll rot(const pll &p) { return { p.first - p.second, p.first + p.second }; } static pll unrot(const pll &p) { assert((p.first + p.second) % 2 == 0); return { (p.first + p.second)/2, (p.first - p.second)/2 }; } void init(const vector<pll> &vals_) { vals = vals_; for (auto &p : vals) p = rot(p); seg.init(vals); } ll count(ll l) { ll sum = 0; for (auto [x, y] : vals) sum += seg.count(x - l, x + l + 1, y - l, y + l + 1); sum -= vals.size(); sum /= 2; return sum; } auto list(ll l) { vector<pair<pll,pll>> vec; for (auto p1 : vals) { auto &[x, y] = p1; auto vec2 = seg.list(x - l, x + l + 1, y - l, y + l + 1); for (auto p2 : vec2) { if (p1 < p2) vec.emplace_back(unrot(p1), unrot(p2)); } } return vec; } }; int main() { cin.tie(0) -> sync_with_stdio(false); int n, k; cin >> n >> k; vector<ll> ans(k); vector<pll> vals(n); for (auto &[x, y] : vals) cin >> x >> y; SquareSeg seg; seg.init(vals); ll l = 0, r = 4.2e9; while (l < r) { ll m = (l + r + 1)/2; if (seg.count(m) < k) l = m; else r = m-1; } vector<ll> vec; for (auto [p1, p2] : seg.list(l)) vec.push_back(abs(p1.first - p2.first) + abs(p1.second - p2.second)); sort(vec.begin(), vec.end()); vec.resize(k, l + 1); for (ll x : vec) cout << x << '\n'; }
#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...