oj.uz

Submission #1050508

# Submission time Handle Problem Language Result Execution time Memory
1050508 2024-08-09T10:19:03 Z ymm Road Construction (JOI21_road_construction) C++17
100 / 100
 9218 ms 185440 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 {
	struct Node {
		Node *l, *r, *p;
		int cnt;
		int x;
 
		static Node *nw() {
			static Node pool[(1<<30)/sizeof(Node)];
			static int p = 0;
			return pool + p++;
		}
	};
	vector<Node *> nodes;
	int m;
 
	Node *add(Node *t, ll p, int x, ll b, ll e) {
		Node *ans = Node::nw();
		ans->p = t;
		ans->cnt = (t? t->cnt: 0) + 1;
		ans->x = x;
		if (e - b == 1)
			return ans;
		if (p < (b + e)/2) {
			ans->l = add(t? t->l: 0, p, x, b, (b+e)/2);
			ans->r = t? t->r: 0;
		} else {
			ans->l = t? t->l: 0;
			ans->r = add(t? t->r: 0, p, x, (b+e)/2, e);
		}
		return ans;
	}
	void init(int n, int m, vector<pll> vals) {
		sort(vals.begin(), vals.end());
		nodes = {nullptr};
		auto it = vals.begin();
		this->m = m;
		Loop (i,0,n) {
			auto t = nodes.back();
			while (it != vals.end() && it->first == i) {
				t = add(t, it->second, i, 0, m);
				it++;
			}
			nodes.push_back(t);
		}
	}
 
	static constexpr int val(const Node *t1, const Node *t2) { return (t2? t2->cnt: 0) - (t1? t1->cnt: 0); }
 
	ll count(Node *t1, Node *t2, ll l, ll r, ll b, ll e) {
		if (r <= b || e <= l || t1 == t2)
			return 0;
		if (l <= b && e <= r)
			return val(t1, t2);
		return count(t1? t1->l: 0, t2->l, l, r, b, (b+e)/2) + count(t1? t1->r: 0, t2->r, l, r, (b+e)/2, e);
	}
	ll count(int l, int r, ll l2, ll r2) {
		return count(nodes[l], nodes[r], l2, r2, 0, m);
	}
 
	void list(Node *t1, Node *t2, vector<pll> &vec, ll l, ll r, ll b, ll e) {
		if (r <= b || e <= l || val(t1, t2) == 0)
			return;
		if (e - b == 1) {
			for (auto t = t2; t != t1; t = t->p)
				vec.push_back({t->x, b});
			return;
		}
		list(t1? t1->l: 0, t2? t2->l: 0, vec, l, r, b, (b+e)/2);
		list(t1? t1->r: 0, t2? t2->r: 0, vec, l, r, (b+e)/2, e);
	}
	vector<pll> list(int l, int r, ll l2, ll r2) {
		vector<pll> ans;
		list(nodes[l], nodes[r], ans, l2, r2, 0, m);
		return ans;
	}
};
 
struct CompSeg {
	Seg seg;
	vector<ll> xs, ys;
 
	int compx(ll x) { return lower_bound(xs.begin(), xs.end(), x) - xs.begin(); }
	int compy(ll y) { return lower_bound(ys.begin(), ys.end(), y) - ys.begin(); }
 
	void init(vector<pll> vals) {
		for (auto [x, y] : vals) {
			xs.push_back(x);
			ys.push_back(y);
		}
		sort(xs.begin(), xs.end());
		sort(ys.begin(), ys.end());
		xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
		ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
		vector<pll> cmped;
		for (auto [x, y] : vals)
			cmped.emplace_back(compx(x), compy(y));
		seg.init(xs.size(), ys.size(), cmped);
	}
 
	ll count(ll l, ll r, ll l2, ll r2) {
		return seg.count(compx(l), compx(r), compy(l2), compy(r2));
	}
	vector<pll> list(ll l, ll r, ll l2, ll r2) {
		auto vec = seg.list(compx(l), compx(r), compy(l2), compy(r2));
		for (auto &[x, y] : vec) {
			x = xs[x];
			y = ys[y];
		}
		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 k) {
		ll sum = 0;
		Loop (i,0,vals.size()) {
			auto [x, y] = vals[i];
			sum += seg.count(x - l, x + l + 1, y - l, y + l + 1);
			if (sum - i - 1 >= 2*k)
				return k;
		}
		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) < 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 45 ms 16324 KB Output is correct
2 Correct 46 ms 16312 KB Output is correct
3 Correct 37 ms 16320 KB Output is correct
4 Correct 36 ms 16324 KB Output is correct
5 Correct 37 ms 16320 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3683 ms 180408 KB Output is correct
2 Correct 3811 ms 180356 KB Output is correct
3 Correct 34 ms 16324 KB Output is correct
4 Correct 3110 ms 181388 KB Output is correct
5 Correct 2887 ms 180516 KB Output is correct
6 Correct 2752 ms 180536 KB Output is correct
7 Correct 3312 ms 180300 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5052 ms 176128 KB Output is correct
2 Correct 5647 ms 176116 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 2028 ms 176384 KB Output is correct
5 Correct 1221 ms 109908 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5052 ms 176128 KB Output is correct
2 Correct 5647 ms 176116 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 2028 ms 176384 KB Output is correct
5 Correct 1221 ms 109908 KB Output is correct
6 Correct 6269 ms 176284 KB Output is correct
7 Correct 6663 ms 176176 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 6521 ms 175444 KB Output is correct
11 Correct 2399 ms 176172 KB Output is correct
12 Correct 1619 ms 110068 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16324 KB Output is correct
2 Correct 46 ms 16312 KB Output is correct
3 Correct 37 ms 16320 KB Output is correct
4 Correct 36 ms 16324 KB Output is correct
5 Correct 37 ms 16320 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 2595 ms 76764 KB Output is correct
8 Correct 2800 ms 75744 KB Output is correct
9 Correct 38 ms 16324 KB Output is correct
10 Correct 2675 ms 76404 KB Output is correct
11 Correct 1617 ms 77640 KB Output is correct
12 Correct 429 ms 42856 KB Output is correct
13 Correct 478 ms 54012 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16324 KB Output is correct
2 Correct 46 ms 16312 KB Output is correct
3 Correct 37 ms 16320 KB Output is correct
4 Correct 36 ms 16324 KB Output is correct
5 Correct 37 ms 16320 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 3683 ms 180408 KB Output is correct
8 Correct 3811 ms 180356 KB Output is correct
9 Correct 34 ms 16324 KB Output is correct
10 Correct 3110 ms 181388 KB Output is correct
11 Correct 2887 ms 180516 KB Output is correct
12 Correct 2752 ms 180536 KB Output is correct
13 Correct 3312 ms 180300 KB Output is correct
14 Correct 5052 ms 176128 KB Output is correct
15 Correct 5647 ms 176116 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 2028 ms 176384 KB Output is correct
18 Correct 1221 ms 109908 KB Output is correct
19 Correct 6269 ms 176284 KB Output is correct
20 Correct 6663 ms 176176 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 6521 ms 175444 KB Output is correct
24 Correct 2399 ms 176172 KB Output is correct
25 Correct 1619 ms 110068 KB Output is correct
26 Correct 2595 ms 76764 KB Output is correct
27 Correct 2800 ms 75744 KB Output is correct
28 Correct 38 ms 16324 KB Output is correct
29 Correct 2675 ms 76404 KB Output is correct
30 Correct 1617 ms 77640 KB Output is correct
31 Correct 429 ms 42856 KB Output is correct
32 Correct 478 ms 54012 KB Output is correct
33 Correct 9218 ms 180360 KB Output is correct
34 Correct 9180 ms 185440 KB Output is correct
35 Correct 8485 ms 183440 KB Output is correct
36 Correct 1008 ms 109348 KB Output is correct
37 Correct 1139 ms 109092 KB Output is correct
38 Correct 1619 ms 119516 KB Output is correct