oj.uz

Submission #1050519

# Submission time Handle Problem Language Result Execution time Memory
1050519 2024-08-09T10:26:11 Z ymm Road Construction (JOI21_road_construction) C++17
32 / 100
 6213 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 {
	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 k, ll l, ll r, ll b, ll e) {
		if (r <= b || e <= l || val(t1, t2) < k)
			return 0;
		if (l <= b && e <= r)
			return val(t1, t2);
		ll ans = 0;
		ans += count(t1? t1->l: 0, t2->l, k, l, r, b, (b+e)/2);
		if (ans >= k)
			return ans;
		ans += count(t1? t1->r: 0, t2->r, k - ans, l, r, (b+e)/2, e);
		return ans;
	}
	ll count(ll k, int l, int r, ll l2, ll r2) {
		return count(nodes[l], nodes[r], k, 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, ll k) {
		return seg.count(k, 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, 2*k + i + 1 - sum);
			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 60 ms 28340 KB Output is correct
2 Correct 62 ms 28344 KB Output is correct
3 Correct 39 ms 16576 KB Output is correct
4 Correct 39 ms 16320 KB Output is correct
5 Correct 56 ms 28852 KB Output is correct
6 Correct 33 ms 26560 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 5748 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2895 ms 181336 KB Output is correct
2 Correct 3040 ms 206344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1192 ms 180192 KB Output is correct
5 Correct 611 ms 112652 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2895 ms 181336 KB Output is correct
2 Correct 3040 ms 206344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1192 ms 180192 KB Output is correct
5 Correct 611 ms 112652 KB Output is correct
6 Correct 6213 ms 339428 KB Output is correct
7 Correct 6125 ms 359248 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 5975 ms 435148 KB Output is correct
11 Correct 1900 ms 334096 KB Output is correct
12 Correct 995 ms 175904 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 28340 KB Output is correct
2 Correct 62 ms 28344 KB Output is correct
3 Correct 39 ms 16576 KB Output is correct
4 Correct 39 ms 16320 KB Output is correct
5 Correct 56 ms 28852 KB Output is correct
6 Correct 33 ms 26560 KB Output is correct
7 Runtime error 2722 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 28340 KB Output is correct
2 Correct 62 ms 28344 KB Output is correct
3 Correct 39 ms 16576 KB Output is correct
4 Correct 39 ms 16320 KB Output is correct
5 Correct 56 ms 28852 KB Output is correct
6 Correct 33 ms 26560 KB Output is correct
7 Runtime error 5748 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -