Submission #1209446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209446		PenguinsAreCute	Road Construction (JOI21_road_construction)	C++17	100 / 100	1148 ms	23896 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#pragma GCC optimize("O3")
struct seg {
	vector<pair<ll,int>> dat;
	int n;
	seg(int _n): n(_n), dat(2*_n,{1e18,0}) {}
	void up(int x, pair<ll,int> v) {
		for(dat[x += n] = v; x >>= 1;)
			dat[x] = min(dat[x<<1], dat[x<<1|1]);
	}
	pair<ll,int> qry(int l, int r) {
		pair<ll,int> ans = {1e18,0};
		for(l+=n,r+=n+1;l<r;l>>=1,r>>=1) {
			if(l&1)
				ans=min(ans,dat[l++]);
			if(r&1)
				ans=min(ans,dat[--r]);
		}
		return ans;
	}
};
vector<ll> solve(vector<pair<int,int>> pts, int k) {
	int n = pts.size();
	sort(pts.begin(),pts.end());
	vector<pair<int,int>> disc(n);
	for(int i=0;i<n;i++)
		disc[i] = {pts[i].second, i};
	sort(disc.begin(),disc.end());
	for(int i=0;i<n;i++)
		disc[i] = {disc[i].second, i};
	sort(disc.begin(),disc.end());

	priority_queue<ll> res;

	seg s(n);
	for(int i=0;i<n;i++) {
		auto [x, y] = pts[i];
		vector<int> taboo;
		for(int j=1;j*j<=4*k;j++) {
			auto [d, p] = s.qry(0,disc[i].second);
			if(d == 1e18)
				break;
			if(res.size() == k && d + x + y > res.top())
				break;
			s.up(disc[p].second, {1e18,p});
			res.push(d + x + y);
			if(res.size() > k)
				res.pop();
			taboo.push_back(p);
		}
		for(auto p: taboo)
			s.up(disc[p].second, {-pts[p].first-pts[p].second,p});
		s.up(disc[i].second, {-x-y,i});
	}

	s = seg(n);
	for(int i=0;i<n;i++) {
		auto [x, y] = pts[i];
		vector<int> taboo;
		for(int j=1;j*j<=4*k;j++) {
			auto [d, p] = s.qry(disc[i].second,n-1);
			if(d == 1e18)
				break;
			if(res.size() == k && d + x - y > res.top())
				break;
			s.up(disc[p].second, {1e18,p});
			res.push(d + x - y);
			if(res.size() > k)
				res.pop();
			taboo.push_back(p);
		}
		for(auto p: taboo)
			s.up(disc[p].second, {-pts[p].first+pts[p].second,p});
		s.up(disc[i].second, {-x+y,i});
	}

	vector<ll> ans;
	while(res.size()) {
		ans.push_back(res.top());
		res.pop();
	}

	return ans;
}
int main() {
	int n, k;
	cin >> n >> k;
	vector<pair<int,int>> xy(n);
	for(int i=0;i<n;i++)
		cin >> xy[i].first >> xy[i].second;
	vector<ll> res = solve(xy, k);
	sort(res.begin(),res.end());
	for(int i=0;i<k;i++)
		cout << res[i] << "\n";
}

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