Submission #465764

#	Time	Username	Problem	Language	Result	Execution time	Memory
465764		koioi.org-dennisstar	Road Construction (JOI21_road_construction)	C++17	33 / 100	1988 ms	1598756 KiB

road_construction

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;

struct node {
	int l, r;
	pair<ll, int> v;
	node() : l(0), r(0), v(1e18, 0) {}
}nd[1<<26];
int nc;

void upd(int i, int i_, int s, int e, int t, ll v) {
	if (s==e) {
		nd[i].v={v, s};
		return ;
	}
	int m=(s+e)/2;
	if (t<=m) {
		nd[i].l=++nc;
		nd[i].r=nd[i_].r;
		upd(nc, nd[i_].l, s, m, t, v);
	}else {
		nd[i].l=nd[i_].l;
		nd[i].r=++nc;
		upd(nc, nd[i_].r, m+1, e, t, v);
	}
	nd[i].v=min(nd[nd[i].l].v, nd[nd[i].r].v);
}

pair<ll, int> get(int i, int s, int e, int l, int r) {
	if (!i||r<l||e<l||r<s) return {1e18, 0};
	if (l<=s&&e<=r) return nd[i].v;
	int m=(s+e)/2;
	return min(get(nd[i].l, s, m, l, r), get(nd[i].r, m+1, e, l, r));
}

void print(int i, int s, int e) {
	if (!i) return ;
	if (s==e) {
		printf("%d : %lld\n", s, nd[i].v.first);
		return ;
	}
	int m=(s+e)/2;
	print(nd[i].l, s, m);
	print(nd[i].r, m+1, e);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
 
	int n, k;
	cin>>n>>k;
	vector<pair<ll, ll>> p(n);
	for (auto &i:p) cin>>i.first>>i.second;

	sort(all(p));
	vector<int> ys(n), yi(n), b(n);
	for (int i=0; i<n; i++) ys[i]=i;
	sort(all(ys), [&](int x, int y) { return p[x].second<p[y].second; });
	for (int i=0; i<n; i++) {
		int j=i;
		for (; j<n&&p[i].second==p[j].second; j++) {
			b[ys[j]]=i;
			yi[ys[j]]=j;
		}
		i=j-1;
	}

	vector<int> ur(n), dr(n);
	priority_queue<pair<ll, int>> pq;
	for (int i=1; i<n; i++) {
		ur[i]=++nc;
		upd(nc, ur[i-1], 0, n-1, yi[i-1], -p[i-1].first+p[i-1].second);
		dr[i]=++nc;
		upd(nc, dr[i-1], 0, n-1, yi[i-1], -p[i-1].first-p[i-1].second);
	}

	auto up = [&](int i) {
		auto k=get(ur[i], 0, n-1, b[i], n-1);
		pq.emplace(-(p[i].first-p[i].second+k.first), i);
		int x=++nc;
		upd(x, ur[i], 0, n-1, k.second, 1e18);
		ur[i]=x;
	};

	auto down = [&](int i) {
		auto k=get(dr[i], 0, n-1, 0, b[i]-1);
		pq.emplace(-(p[i].first+p[i].second+k.first), i+n);
		int x=++nc;
		upd(x, dr[i], 0, n-1, k.second, 1e18);
		dr[i]=x;
	};

	for (int i=1; i<n; i++) up(i), down(i);

	while (k--) {
		auto [v, i]=pq.top();
		pq.pop();
		cout<<-v<<'\n';
		if (i<n) up(i);
		else down(i-n);
	}

	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35