oj.uz

Submission #1050489

# Submission time Handle Problem Language Result Execution time Memory
1050489 2024-08-09T10:11:40 Z ymm Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 185092 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 || !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 54 ms 16368 KB Output is correct
2 Correct 57 ms 16828 KB Output is correct
3 Correct 39 ms 16324 KB Output is correct
4 Correct 38 ms 16580 KB Output is correct
5 Correct 40 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 3945 ms 183724 KB Output is correct
2 Correct 3866 ms 183384 KB Output is correct
3 Correct 35 ms 16324 KB Output is correct
4 Correct 3385 ms 184416 KB Output is correct
5 Correct 3074 ms 183296 KB Output is correct
6 Correct 2944 ms 183648 KB Output is correct
7 Correct 3620 ms 185092 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5469 ms 181472 KB Output is correct
2 Correct 5923 ms 181372 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2168 ms 179124 KB Output is correct
5 Correct 1558 ms 115756 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5469 ms 181472 KB Output is correct
2 Correct 5923 ms 181372 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2168 ms 179124 KB Output is correct
5 Correct 1558 ms 115756 KB Output is correct
6 Correct 6578 ms 181392 KB Output is correct
7 Correct 6658 ms 182756 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 6252 ms 180524 KB Output is correct
11 Correct 2387 ms 179052 KB Output is correct
12 Correct 1592 ms 115500 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 16368 KB Output is correct
2 Correct 57 ms 16828 KB Output is correct
3 Correct 39 ms 16324 KB Output is correct
4 Correct 38 ms 16580 KB Output is correct
5 Correct 40 ms 16320 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 3417 ms 78544 KB Output is correct
8 Correct 3457 ms 78552 KB Output is correct
9 Correct 40 ms 16580 KB Output is correct
10 Correct 3189 ms 79200 KB Output is correct
11 Correct 1718 ms 78236 KB Output is correct
12 Correct 545 ms 44648 KB Output is correct
13 Correct 518 ms 55908 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 16368 KB Output is correct
2 Correct 57 ms 16828 KB Output is correct
3 Correct 39 ms 16324 KB Output is correct
4 Correct 38 ms 16580 KB Output is correct
5 Correct 40 ms 16320 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 3945 ms 183724 KB Output is correct
8 Correct 3866 ms 183384 KB Output is correct
9 Correct 35 ms 16324 KB Output is correct
10 Correct 3385 ms 184416 KB Output is correct
11 Correct 3074 ms 183296 KB Output is correct
12 Correct 2944 ms 183648 KB Output is correct
13 Correct 3620 ms 185092 KB Output is correct
14 Correct 5469 ms 181472 KB Output is correct
15 Correct 5923 ms 181372 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2168 ms 179124 KB Output is correct
18 Correct 1558 ms 115756 KB Output is correct
19 Correct 6578 ms 181392 KB Output is correct
20 Correct 6658 ms 182756 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 6252 ms 180524 KB Output is correct
24 Correct 2387 ms 179052 KB Output is correct
25 Correct 1592 ms 115500 KB Output is correct
26 Correct 3417 ms 78544 KB Output is correct
27 Correct 3457 ms 78552 KB Output is correct
28 Correct 40 ms 16580 KB Output is correct
29 Correct 3189 ms 79200 KB Output is correct
30 Correct 1718 ms 78236 KB Output is correct
31 Correct 545 ms 44648 KB Output is correct
32 Correct 518 ms 55908 KB Output is correct
33 Execution timed out 10064 ms 183332 KB Time limit exceeded
34 Halted 0 ms 0 KB -