oj.uz

Submission #1049603

# Submission time Handle Problem Language Result Execution time Memory
1049603 2024-08-09T02:06:34 Z ymm Road Construction (JOI21_road_construction) C++17
32 / 100
 10000 ms 2097152 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, int l2, int 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<int> 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 = 4e9;
	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 53 ms 26300 KB Output is correct
2 Correct 54 ms 26300 KB Output is correct
3 Correct 37 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6032 ms 133568 KB Output is correct
2 Correct 5932 ms 133832 KB Output is correct
3 Correct 30 ms 14532 KB Output is correct
4 Correct 6455 ms 132556 KB Output is correct
5 Runtime error 3127 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10044 ms 131408 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 10044 ms 131408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 26300 KB Output is correct
2 Correct 54 ms 26300 KB Output is correct
3 Correct 37 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 4829 ms 59840 KB Output is correct
8 Correct 4727 ms 59952 KB Output is correct
9 Correct 33 ms 14276 KB Output is correct
10 Correct 3120 ms 57856 KB Output is correct
11 Correct 2695 ms 57508 KB Output is correct
12 Correct 1224 ms 28284 KB Output is correct
13 Correct 1959 ms 37620 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 26300 KB Output is correct
2 Correct 54 ms 26300 KB Output is correct
3 Correct 37 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 6032 ms 133568 KB Output is correct
8 Correct 5932 ms 133832 KB Output is correct
9 Correct 30 ms 14532 KB Output is correct
10 Correct 6455 ms 132556 KB Output is correct
11 Runtime error 3127 ms 2097152 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -