제출 #1197714

#제출 시각아이디문제언어결과실행 시간메모리
1197714HanksburgerRoad Construction (JOI21_road_construction)C++20
100 / 100
4085 ms1570060 KiB
#include <bits/stdc++.h> #define int long long using namespace std; struct node { node *lc, *rc; int l, r; pair<int, int> val; node(int l, int r) : lc(0), rc(0), l(l), r(r), val({1e18, 0}) {} } *empt, *lft[250005], *rght[250005], *root[750005]; set<pair<int, pair<int, int> > > s; int lvers[250005], rvers[250005]; pair<int, int> points[250005]; vector<pair<int, int> > vec; void build(node *i) { if (i->l==i->r) return; int mid=(i->l+i->r)/2; i->lc=new node(i->l, mid); i->rc=new node(mid+1, i->r); build(i->lc); build(i->rc); } void upd1(node *pre, node *i, int x, int y) { if (i->l==i->r) { i->val={y, x}; return; } int mid=(i->l+i->r)/2; if (x<=mid) { i->lc=new node(i->l, mid); upd1(pre->lc, i->lc, x, y); i->rc=pre->rc; } else { i->lc=pre->lc; i->rc=new node(mid+1, i->r); upd1(pre->rc, i->rc, x, y); } i->val=min(i->lc->val, i->rc->val); } void upd2(node *em, node *pre, node *i, int x) { if (i->l==i->r) return; int mid=(i->l+i->r)/2; if (x<=mid) { i->lc=new node(i->l, mid); upd2(em->lc, pre->lc, i->lc, x); i->rc=em->rc; } else { i->lc=pre->lc; i->rc=new node(mid+1, i->r); upd2(em->rc, pre->rc, i->rc, x); } i->val=min(i->lc->val, i->rc->val); } void upd3(node *em, node *pre, node *i, int x) { if (i->l==i->r) return; int mid=(i->l+i->r)/2; if (x<=mid) { i->lc=new node(i->l, mid); upd3(em->lc, pre->lc, i->lc, x); i->rc=pre->rc; } else { i->lc=em->lc; i->rc=new node(mid+1, i->r); upd3(em->rc, pre->rc, i->rc, x); } i->val=min(i->lc->val, i->rc->val); } int dist(int x, int y) { return abs(points[x].first-points[y].first)+abs(points[x].second-points[y].second); } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k, cur; cin >> n >> k; for (int i=1; i<=n; i++) cin >> points[i].first >> points[i].second; sort(points+1, points+n+1); for (int i=1; i<=n; i++) vec.push_back({-points[i].second, i}); sort(vec.begin(), vec.end()); empt=lft[0]=rght[0]=new node(1, n); build(empt); for (int i=1; i<=n; i++) { int x=vec[i-1].second; lft[i]=new node(1, n); rght[i]=new node(1, n); upd1(lft[i-1], lft[i], x, points[x].second-points[x].first); upd1(rght[i-1], rght[i], x, points[x].first+points[x].second); root[i*2-1]=new node(1, n); root[i*2]=new node(1, n); upd2(empt, lft[i-1], root[i*2-1], x); upd3(empt, rght[i-1], root[i*2], x); lvers[x]=i*2-1; rvers[x]=i*2; if ((root[i*2-1]->val).first<1e15) { int y=(root[i*2-1]->val).second; s.insert({dist(x, y), {x, y}}); //cout << "left x y " << x << ' ' << y << '\n'; } if ((root[i*2]->val).first<1e15) { int y=(root[i*2]->val).second; s.insert({dist(x, y), {x, y}}); //cout << "right x y " << x << ' ' << y << '\n'; } } cur=n*2; while (k--) { cout << (s.begin()->first) << '\n'; int x=(s.begin()->second).first, y=(s.begin()->second).second; //cout << "s element " << (s.begin()->first) << ' ' << x << ' ' << y << '\n'; s.erase(s.begin()); if (x<y) { cur++; root[cur]=new node(1, n); upd1(root[rvers[x]], root[cur], y, 1e18); rvers[x]=cur; if ((root[cur]->val).first<1e15) { y=(root[cur]->val).second; s.insert({dist(x, y), {x, y}}); //cout << "new right x y " << x << ' ' << y << '\n'; } } else { cur++; root[cur]=new node(1, n); upd1(root[lvers[x]], root[cur], y, 1e18); lvers[x]=cur; if ((root[cur]->val).first<1e15) { y=(root[cur]->val).second; s.insert({dist(x, y), {x, y}}); //cout << "new left x y " << x << ' ' << y << '\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...