제출 #1209478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209478		PenguinsAreCute	Road Construction (JOI21_road_construction)	C++17	100 / 100	2419 ms	49244 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 20;
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);
	vector<int> taboo[n];
	bool active[n];
	memset(active,1,sizeof(active));
	// NK^0.25 * log N
	for(int l=0;l<M;l++) {
		for(int i=0;i<n;i++) {
			auto [x, y] = pts[i];
			if(active[i]) {
				for(auto p: taboo[i])
					s.up(disc[p].second, {1e18,p});
				for(int j=0;j*j*M*M<=4*k;j++) {
					auto [d, p] = s.qry(0,disc[i].second);
					if(d == 1e18) {
						active[i] = 0;
						break;
					}
					if(res.size() == k && d + x + y > res.top()) {
						active[i] = 0;
						break;
					}
					s.up(disc[p].second, {1e18,p});
					res.push(d + x + y);
					if(res.size() > k)
						res.pop();
					taboo[i].push_back(p);
				}
				for(auto p: taboo[i])
					s.up(disc[p].second, {-pts[p].first-pts[p].second,p});
			}
			s.up(disc[i].second, {-x-y,i});
		}
		s = seg(n);
	}

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

	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