제출 #1315779

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315779		vlomaczk	Road Construction (JOI21_road_construction)	C++20	7 / 100	9144 ms	29788 KiB

road_construction

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename TY>
struct MultiOrderedSet {
	ordered_set<pair<TY, int>> os;
	int cnt = 0;
	void insert(TY x) {
		os.insert({x, cnt++});
	}
	void erase(TY x) {
		int i = os.order_of_key({x,-1});
		assert(i < os.size());
		os.erase(*os.find_by_order(i));
	}
	TY first() { return os.begin()->first; }
	TY last() { return os.rbegin()->first; }
	void clear() {
		while(os.size()) os.erase(*os.begin());
	}
	int size() { return os.size(); }
	bool empty() { return os.empty(); }
	int order_of_key(TY x) {
		return os.order_of_key({x, -1});
	}
	TY find_by_order(ll x) {
		return os.find_by_order(x)->first;
	}
	ll amount(ll a, ll b) {
		return order_of_key(b+1) - order_of_key(a);
	}
};

struct Point {
	ll x, y;
	friend bool operator<(Point a, Point b) {
		return a.y < b.y;
	}
};

ll M = 250'010;
vector<ll> cnt(M,1);
ll n;
ll inf = 1e18;

vector<Point> pkt;
vector<ll> X, Y;
ll base = 1<<18;
ll numer = 1;

vector<ll> dists;

ll count(ll d) {
	vector<pair<ll, ll>> sweep;
	for(int i=0; i<n; ++i) {
		sweep.push_back({pkt[i].y - d - 1, i});
		sweep.push_back({pkt[i].y, i});
	}
	MultiOrderedSet<ll> mos;
	ll sum = 0;
	sort(sweep.begin(), sweep.end());
	for(auto[poz, i] : sweep) {
		if(pkt[i].y > poz) {
			sum -= mos.amount(pkt[i].x-d, pkt[i].x+d);
		} else {
			sum += mos.amount(pkt[i].x-d, pkt[i].x+d);
			mos.insert(pkt[i].x);
		}
	}
	return sum;
}

vector<ll> get_dists(ll d) {
	vector<ll> dists;
	
	return dists;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll k;
	cin >> n >> k;
	pkt.resize(n);
	for(ll i=0; i<n; ++i) {
		ll x,y;
		cin >> x >> y;
		pkt[i] = {x+y,x-y};
	}
	sort(pkt.begin(), pkt.end());
	ll lo = 0;
	ll hi = 4e9;
	while(lo < hi) {
		ll mid = (lo+hi)/2;
		if(count(mid) < k) lo = mid+1;
		else hi = mid;
	}
	cout << lo << "\n";
	vector<ll> dists = get_dists(lo);
	sort(dists.begin(), dists.end());
	// for(int i=0; i<k; ++i) cout << dists[i] << " "; cout << "\n";

	return 0;
}

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