Submission #1110521

#TimeUsernameProblemLanguageResultExecution timeMemory
1110521onbertRoad Construction (JOI21_road_construction)C++17
5 / 100
10057 ms191820 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 250005, maxN = 1e6 + 5, INF = 1e10; int n, k; pair<int,int> a[maxn]; int sz; vector<int> vals = {-INF}; 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; } }; 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)/2; 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)/2; 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)/2; 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; } 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)); pair<int,int> b[n+1]; priority_queue<thing> pq; for (int i=2;i<=n;i++) { b[i] = {0, 1}; int l = b[i].first+1, r = INF; while (l < r) { int mid = (l+r)/2; if (cunt(i, mid) == b[i].second) l = mid+1; else r = mid; } pq.push({i, l, cunt(i, l)}); // cout << i << " " << l << " " << cunt(i, l) << endl; } int total = 0; while (true) { int dist = pq.top().dist, cnt = pq.top().cnt, id = pq.top().id; pq.pop(); // cout << id << " " << b[id].second << " " << cnt << endl; if (id==2 && b[id].second==2) return 0; 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; } pq.push({id, l, cunt(id, l)}); } }
#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...