oj.uz

Submission #1049605

# Submission time Handle Problem Language Result Execution time Memory
1049605 2024-08-09T02:10:27 Z ymm Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 134932 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 14524 KB Output is correct
2 Correct 53 ms 14752 KB Output is correct
3 Correct 32 ms 14272 KB Output is correct
4 Correct 32 ms 14276 KB Output is correct
5 Correct 37 ms 14532 KB Output is correct
6 Correct 4 ms 604 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6095 ms 134800 KB Output is correct
2 Correct 6323 ms 133616 KB Output is correct
3 Correct 30 ms 14532 KB Output is correct
4 Correct 6165 ms 133484 KB Output is correct
5 Correct 6366 ms 134748 KB Output is correct
6 Correct 6373 ms 133784 KB Output is correct
7 Correct 6250 ms 134932 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10065 ms 127304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10065 ms 127304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 14524 KB Output is correct
2 Correct 53 ms 14752 KB Output is correct
3 Correct 32 ms 14272 KB Output is correct
4 Correct 32 ms 14276 KB Output is correct
5 Correct 37 ms 14532 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4633 ms 58224 KB Output is correct
8 Correct 4647 ms 58192 KB Output is correct
9 Correct 32 ms 14528 KB Output is correct
10 Correct 3013 ms 56204 KB Output is correct
11 Correct 2623 ms 55344 KB Output is correct
12 Correct 1163 ms 26704 KB Output is correct
13 Correct 1941 ms 35940 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 14524 KB Output is correct
2 Correct 53 ms 14752 KB Output is correct
3 Correct 32 ms 14272 KB Output is correct
4 Correct 32 ms 14276 KB Output is correct
5 Correct 37 ms 14532 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 6095 ms 134800 KB Output is correct
8 Correct 6323 ms 133616 KB Output is correct
9 Correct 30 ms 14532 KB Output is correct
10 Correct 6165 ms 133484 KB Output is correct
11 Correct 6366 ms 134748 KB Output is correct
12 Correct 6373 ms 133784 KB Output is correct
13 Correct 6250 ms 134932 KB Output is correct
14 Execution timed out 10065 ms 127304 KB Time limit exceeded
15 Halted 0 ms 0 KB -