Submission #1110856

#TimeUsernameProblemLanguageResultExecution timeMemory
1110856onbertRoad Construction (JOI21_road_construction)C++17
0 / 100
10054 ms198580 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 500005, maxN = 1e6 + 5, INF = 2e9 + 10; int n, k; pair<int,int> a[maxn]; int sz; vector<int> vals = {-(int)1e18}; int ldc(int x) {return lower_bound(vals.begin(), vals.end(), x) - vals.begin();} int rdc(int x) {return upper_bound(vals.begin(), vals.end(), x) - vals.begin() - 1;} struct node { int lpt, rpt, val; }; struct thing { int id, dist, cnt; bool operator < (const thing &b) const { return dist > b.dist; } }; pair<int,int> b[maxn]; vector<node> seg[maxN]; void build(int id, int l, int r) { seg[id] = {{0, 0, 0}}; if (l==r) return; int mid = (l+r) >> 1; build(id*2, l, mid); build(id*2+1, mid+1, r); } void update(int id, int l, int r, int target) { if (r<target || target<l) return; if (l==r) { int val = seg[id].back().val + 1; seg[id].push_back({0, 0, val}); return; } int mid = (l+r) >> 1; update(id*2, l, mid, target); update(id*2+1, mid+1, r, target); int val = seg[id*2].back().val + seg[id*2+1].back().val; seg[id].push_back({(int)seg[id*2].size() - 1, (int)seg[id*2+1].size() - 1, val}); } int qry(int id, int pt, int l, int r, int findl, int findr) { if (r<findl || findr<l) return 0; if (findl<=l && r<=findr) return seg[id][pt].val; int mid = (l+r) >> 1; int lhs = qry(id*2, seg[id][pt].lpt, l, mid, findl, findr); int rhs = qry(id*2+1, seg[id][pt].rpt, mid+1, r, findl, findr); return lhs + rhs; } int cunt(int id, int dist) { int L = ldc(a[id].second - dist), R = rdc(a[id].second + dist); int val = qry(1, id, 1, sz, L, R); int x = lower_bound(a+1, a+n+1, make_pair(a[id].first - dist, -INF)) - a - 1; // cout << val << " " << x << endl; val -= qry(1, x, 1, sz, L, R); return val; } priority_queue<thing> pq; signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (int i=1;i<=n;i++) { int x, y; cin >> x >> y; a[i] = {x+y, x-y}; vals.push_back(x-y); } sort(a+1, a+n+1); sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); sz = vals.size() - 1; build(1, 1, sz); for (int i=1;i<=n;i++) update(1, 1, sz, ldc(a[i].second)); for (int i=2;i<=n;i++) { b[i] = {0, 1}; int l = 1, r = INF; while (l < r) { int mid = (l+r)/2; if (cunt(i, mid) == b[i].second) l = mid+1; else r = mid; } int x = cunt(i, l); pq.push({i, l, x}); // cout << i << " " << l << " " << cunt(i, l) << endl; } // assert(false); int total = 0; while (true) { int id = pq.top().id, dist = pq.top().dist, cnt = pq.top().cnt; pq.pop(); for (;b[id].second<cnt;b[id].second++) { cout << dist << '\n'; total++; if (total == k) return 0; } if (b[id].second == id) continue; b[id].first = dist; int l = dist+1, r = INF; while (l < r) { int mid = (l+r)/2; if (cunt(id, mid) == b[id].second) l = mid+1; else r = mid; } int x = cunt(id, l); pq.push({id, l, x}); } }
#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...