oj.uz

Submission #1049678

# Submission time Handle Problem Language Result Execution time Memory
1049678 2024-08-09T03:53:03 Z ymm Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 181384 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;

#pragma GCC optimize("O3,unroll-loops")
 
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 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 = 4.2e9;
	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 46 ms 16576 KB Output is correct
2 Correct 44 ms 16312 KB Output is correct
3 Correct 36 ms 16640 KB Output is correct
4 Correct 39 ms 16832 KB Output is correct
5 Correct 37 ms 16316 KB Output is correct
6 Correct 4 ms 2648 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8098 ms 180356 KB Output is correct
2 Correct 8170 ms 180820 KB Output is correct
3 Correct 34 ms 16284 KB Output is correct
4 Correct 8314 ms 181384 KB Output is correct
5 Correct 8084 ms 180364 KB Output is correct
6 Correct 8076 ms 180360 KB Output is correct
7 Correct 8208 ms 180364 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16576 KB Output is correct
2 Correct 44 ms 16312 KB Output is correct
3 Correct 36 ms 16640 KB Output is correct
4 Correct 39 ms 16832 KB Output is correct
5 Correct 37 ms 16316 KB Output is correct
6 Correct 4 ms 2648 KB Output is correct
7 Correct 4363 ms 77268 KB Output is correct
8 Correct 4330 ms 77024 KB Output is correct
9 Correct 40 ms 16324 KB Output is correct
10 Correct 3662 ms 76400 KB Output is correct
11 Correct 3559 ms 76968 KB Output is correct
12 Correct 681 ms 42856 KB Output is correct
13 Correct 830 ms 54180 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16576 KB Output is correct
2 Correct 44 ms 16312 KB Output is correct
3 Correct 36 ms 16640 KB Output is correct
4 Correct 39 ms 16832 KB Output is correct
5 Correct 37 ms 16316 KB Output is correct
6 Correct 4 ms 2648 KB Output is correct
7 Correct 8098 ms 180356 KB Output is correct
8 Correct 8170 ms 180820 KB Output is correct
9 Correct 34 ms 16284 KB Output is correct
10 Correct 8314 ms 181384 KB Output is correct
11 Correct 8084 ms 180364 KB Output is correct
12 Correct 8076 ms 180360 KB Output is correct
13 Correct 8208 ms 180364 KB Output is correct
14 Execution timed out 10051 ms 176124 KB Time limit exceeded
15 Halted 0 ms 0 KB -