oj.uz

Submission #1050600

# Submission time Handle Problem Language Result Execution time Memory
1050600 2024-08-09T11:40:22 Z ymm Road Construction (JOI21_road_construction) C++17
100 / 100
 4426 ms 184456 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);
		sort(vals.begin(), vals.end());
		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 43 ms 16324 KB Output is correct
2 Correct 43 ms 16568 KB Output is correct
3 Correct 37 ms 16320 KB Output is correct
4 Correct 36 ms 16324 KB Output is correct
5 Correct 36 ms 16320 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 981 ms 182868 KB Output is correct
2 Correct 973 ms 182980 KB Output is correct
3 Correct 34 ms 16324 KB Output is correct
4 Correct 822 ms 183940 KB Output is correct
5 Correct 773 ms 183040 KB Output is correct
6 Correct 725 ms 182844 KB Output is correct
7 Correct 1014 ms 183380 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1576 ms 180260 KB Output is correct
2 Correct 2200 ms 180260 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 527 ms 178744 KB Output is correct
5 Correct 547 ms 114220 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1576 ms 180260 KB Output is correct
2 Correct 2200 ms 180260 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 527 ms 178744 KB Output is correct
5 Correct 547 ms 114220 KB Output is correct
6 Correct 2432 ms 180272 KB Output is correct
7 Correct 2391 ms 180384 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2482 ms 179560 KB Output is correct
11 Correct 601 ms 178724 KB Output is correct
12 Correct 682 ms 114220 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16324 KB Output is correct
2 Correct 43 ms 16568 KB Output is correct
3 Correct 37 ms 16320 KB Output is correct
4 Correct 36 ms 16324 KB Output is correct
5 Correct 36 ms 16320 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 1655 ms 77392 KB Output is correct
8 Correct 1770 ms 77272 KB Output is correct
9 Correct 36 ms 16324 KB Output is correct
10 Correct 1245 ms 77024 KB Output is correct
11 Correct 676 ms 76264 KB Output is correct
12 Correct 293 ms 42936 KB Output is correct
13 Correct 267 ms 55428 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16324 KB Output is correct
2 Correct 43 ms 16568 KB Output is correct
3 Correct 37 ms 16320 KB Output is correct
4 Correct 36 ms 16324 KB Output is correct
5 Correct 36 ms 16320 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 981 ms 182868 KB Output is correct
8 Correct 973 ms 182980 KB Output is correct
9 Correct 34 ms 16324 KB Output is correct
10 Correct 822 ms 183940 KB Output is correct
11 Correct 773 ms 183040 KB Output is correct
12 Correct 725 ms 182844 KB Output is correct
13 Correct 1014 ms 183380 KB Output is correct
14 Correct 1576 ms 180260 KB Output is correct
15 Correct 2200 ms 180260 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 527 ms 178744 KB Output is correct
18 Correct 547 ms 114220 KB Output is correct
19 Correct 2432 ms 180272 KB Output is correct
20 Correct 2391 ms 180384 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 2482 ms 179560 KB Output is correct
24 Correct 601 ms 178724 KB Output is correct
25 Correct 682 ms 114220 KB Output is correct
26 Correct 1655 ms 77392 KB Output is correct
27 Correct 1770 ms 77272 KB Output is correct
28 Correct 36 ms 16324 KB Output is correct
29 Correct 1245 ms 77024 KB Output is correct
30 Correct 676 ms 76264 KB Output is correct
31 Correct 293 ms 42936 KB Output is correct
32 Correct 267 ms 55428 KB Output is correct
33 Correct 4410 ms 184456 KB Output is correct
34 Correct 4426 ms 183176 KB Output is correct
35 Correct 3160 ms 181172 KB Output is correct
36 Correct 632 ms 106900 KB Output is correct
37 Correct 723 ms 106948 KB Output is correct
38 Correct 692 ms 117512 KB Output is correct