oj.uz

Submission #1049673

# Submission time Handle Problem Language Result Execution time Memory
1049673 2024-08-09T03:50:13 Z ymm Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 181584 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 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 57 ms 16308 KB Output is correct
2 Correct 45 ms 16316 KB Output is correct
3 Correct 37 ms 16580 KB Output is correct
4 Correct 36 ms 16324 KB Output is correct
5 Correct 38 ms 16320 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 7194 ms 180552 KB Output is correct
2 Correct 7718 ms 180308 KB Output is correct
3 Correct 34 ms 16836 KB Output is correct
4 Correct 7448 ms 181584 KB Output is correct
5 Correct 7896 ms 180352 KB Output is correct
6 Correct 7487 ms 180360 KB Output is correct
7 Correct 7786 ms 180360 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16308 KB Output is correct
2 Correct 45 ms 16316 KB Output is correct
3 Correct 37 ms 16580 KB Output is correct
4 Correct 36 ms 16324 KB Output is correct
5 Correct 38 ms 16320 KB Output is correct
6 Correct 4 ms 2648 KB Output is correct
7 Correct 4139 ms 76288 KB Output is correct
8 Correct 4302 ms 76764 KB Output is correct
9 Correct 36 ms 16576 KB Output is correct
10 Correct 3675 ms 77684 KB Output is correct
11 Correct 3513 ms 76876 KB Output is correct
12 Correct 649 ms 42808 KB Output is correct
13 Correct 827 ms 53936 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16308 KB Output is correct
2 Correct 45 ms 16316 KB Output is correct
3 Correct 37 ms 16580 KB Output is correct
4 Correct 36 ms 16324 KB Output is correct
5 Correct 38 ms 16320 KB Output is correct
6 Correct 4 ms 2648 KB Output is correct
7 Correct 7194 ms 180552 KB Output is correct
8 Correct 7718 ms 180308 KB Output is correct
9 Correct 34 ms 16836 KB Output is correct
10 Correct 7448 ms 181584 KB Output is correct
11 Correct 7896 ms 180352 KB Output is correct
12 Correct 7487 ms 180360 KB Output is correct
13 Correct 7786 ms 180360 KB Output is correct
14 Execution timed out 10061 ms 176176 KB Time limit exceeded
15 Halted 0 ms 0 KB -