Submission #1049605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049605		ymm	Road Construction (JOI21_road_construction)	C++17	38 / 100	10065 ms	134932 KiB

road_construction

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

struct Seg {
	vector<vector<pll>> ys;
	int n;

	static bool cmp(const pll &a, const pll &b) {
		return a.second < b.second;
	}

	void init(const pll *&ptr, const pll *end, int i, int b, int e)
	{
		if (e - b == 1) {
			ys[i].clear();
			while (ptr != end && ptr->first == b)
				ys[i].push_back(*ptr++);
			return;
		}
		init(ptr, end, 2*i+1, b, (b+e)/2);
		init(ptr, end, 2*i+2, (b+e)/2, e);
		ys[i].resize(ys[2*i+1].size() + ys[2*i+2].size());
		merge(ys[2*i+1].begin(), ys[2*i+1].end(),
		      ys[2*i+2].begin(), ys[2*i+2].end(),
		      ys[i].begin(), cmp);
	}

	void init(int n, vector<pll> vals) {
		this->n = n;
		ys.resize(n*4);
		sort(vals.begin(), vals.end());
		const pll *ptr = vals.data();
		init(ptr, ptr + vals.size(), 0, 0, n);
	}

	typedef decltype(ys[0].begin()) iter;

	template<class Fn>
	void range_query(Fn fn, int l, int r, ll l2, ll r2, int i, int b, int e) {
		if (l <= b && e <= r) {
			iter it1 = lower_bound(ys[i].begin(), ys[i].end(), pll{INT_MIN, l2}, cmp);
			iter it2 = lower_bound(ys[i].begin(), ys[i].end(), pll{INT_MIN, r2}, cmp);
			return fn(it1, it2);
		}
		if (r <= b || e <= l)
			return;
		range_query(fn, l, r, l2, r2, 2*i+1, b, (b+e)/2);
		range_query(fn, l, r, l2, r2, 2*i+2, (b+e)/2, e);
	}

	ll count(int l, int r, ll l2, ll r2) {
		ll ans = 0;
		range_query([&](iter it1, iter it2) { ans += it2 - it1; }, l, r, l2, r2, 0, 0, n);
		return ans;
	}
	vector<pll> list(int l, int r, ll l2, ll r2) {
		vector<pll> ans;
		range_query([&](iter it1, iter it2) { ans.insert(ans.end(), it1, it2); }, l, r, l2, r2, 0, 0, n);
		return ans;
	}
};

struct CompSeg {
	Seg seg;
	vector<ll> xs;

	int comp(ll x) { return lower_bound(xs.begin(), xs.end(), x) - xs.begin(); }

	void init(vector<pll> vals) {
		for (auto [x, _] : vals)
			xs.push_back(x);
		sort(xs.begin(), xs.end());
		xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
		vector<pll> cmped;
		for (auto [x, y] : vals)
			cmped.emplace_back(comp(x), y);
		seg.init(xs.size(), cmped);
	}

	ll count(ll l, ll r, ll l2, ll r2) {
		return seg.count(comp(l), comp(r), l2, r2);
	}
	vector<pll> list(ll l, ll r, ll l2, ll r2) {
		auto vec = seg.list(comp(l), comp(r), l2, r2);
		for (auto &[x, y] : vec)
			x = xs[x];
		return vec;
	}
};

struct SquareSeg {
	CompSeg seg;
	vector<pll> vals;

	static pll rot(const pll &p) {
		return { p.first - p.second, p.first + p.second };
	}
	static pll unrot(const pll &p) {
		assert((p.first + p.second) % 2 == 0);
		return { (p.first + p.second)/2, (p.first - p.second)/2 };
	}

	void init(const vector<pll> &vals_) {
		vals = vals_;
		for (auto &p : vals)
			p = rot(p);
		seg.init(vals);
	}

	ll count(ll l) {
		ll sum = 0;
		for (auto [x, y] : vals)
			sum += seg.count(x - l, x + l + 1, y - l, y + l + 1);
		sum -= vals.size();
		sum /= 2;
		return sum;
	}
	auto list(ll l) {
		vector<pair<pll,pll>> vec;
		for (auto p1 : vals) {
			auto &[x, y] = p1;
			auto vec2 = seg.list(x - l, x + l + 1, y - l, y + l + 1);
			for (auto p2 : vec2) {
				if (p1 < p2)
					vec.emplace_back(unrot(p1), unrot(p2));
			}
		}
		return vec;
	}
};

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	vector<ll> ans(k);
	vector<pll> vals(n);
	for (auto &[x, y] : vals)
		cin >> x >> y;
	SquareSeg seg;
	seg.init(vals);
	ll l = 0, r = 4.2e9;
	while (l < r) {
		ll m = (l + r + 1)/2;
		if (seg.count(m) < k)
			l = m;
		else
			r = m-1;
	}
	vector<ll> vec;
	for (auto [p1, p2] : seg.list(l))
		vec.push_back(abs(p1.first - p2.first) + abs(p1.second - p2.second));
	sort(vec.begin(), vec.end());
	vec.resize(k, l + 1);
	for (ll x : vec)
		cout << x << '\n';
}

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