Submission #1111940

#TimeUsernameProblemLanguageResultExecution timeMemory
1111940onbertRoad Construction (JOI21_road_construction)C++17
0 / 100
83 ms16368 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 250005, 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 = {{0, 0, 0}}; vector<int> lg = {1}; void build(int id, int l, int r) { seg.push_back({0, 0, 0}); if (l==r) return; int mid = (l+r) >> 1; seg[id].lpt = seg.size(); build(id*2, l, mid); seg[id].rpt = seg.size(); build(id*2+1, mid+1, r); } void update(int id, int l, int r, int target) { seg[id].val++; if (l==r) return; int mid = (l+r)/2; if (l<=target && target<=mid) { seg.push_back(seg[seg[id].lpt]); seg[id].lpt = seg.size() - 1; update(seg.size() - 1, l, mid, target); } if (mid+1<=target && target<=r) { seg.push_back(seg[seg[id].rpt]); seg[id].rpt = seg.size() - 1; update(seg.size() - 1, mid+1, r, target); } } int qry(int id, int l, int r, int findl, int findr) { if (r<findl || findr<l) return 0; if (findl<=l && r<=findr) return seg[id].val; int mid = (l+r) >> 1; int lhs = qry(seg[id].lpt, l, mid, findl, findr); int rhs = qry(seg[id].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(lg[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(lg[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++) { seg.push_back(seg[lg.back()]); lg.push_back(seg.size() - 1); update(seg.size() - 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; } 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...