oj.uz

Submission #484461

# Submission time Handle Problem Language Result Execution time Memory
484461 2021-11-03T14:23:18 Z valerikk Hamburg Steak (JOI20_hamburg) C++17
100 / 100
 821 ms 64768 KB 
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int INF = 1'000'000'000;
const int N = 800005;


struct Point {
	int x, y;
};

struct Seg {
	int l, r;

	Seg() : l(1), r(N) {}

	Seg(int l, int r) : l(l), r(r) {}
};

void self_intersect(Seg &a, const Seg &b) {
	a.l = max(a.l, b.l);
	a.r = min(a.r, b.r);
}

Seg intersect(Seg a, const Seg &b) {
	self_intersect(a, b);
	return a;
}

bool inside(int x, const Seg &s) {
	return x >= s.l && x <= s.r;
}

struct Rect {
	Seg x, y;

	Rect() : x{}, y{} {}

	Rect(const Seg &x, const Seg &y) : x(x), y(y) {}
};

istream &operator>>(istream &stream, Rect &r) {
	stream >> r.x.l >> r.y.l >> r.x.r >> r.y.r;
	return stream;
}

void self_intersect(Rect &a, const Rect &b) {
	self_intersect(a.x, b.x);
	self_intersect(a.y, b.y);
}

Rect intersect(Rect a, const Rect &b) {
	self_intersect(a, b);
	return a;
}

bool inside(const Point &p, const Rect &r) {
	return inside(p.x, r.x) && inside(p.y, r.y);
}

int k;
vector<int> vals;

void adjust(int &val) {
	val = lower_bound(vals.begin(), vals.end(), val) - vals.begin();
}

void output(const vector<Point> &pts) {
	for (const auto &[x, y] : pts) {
		cout << vals[x] << " " << vals[y] << "\n";
	}
	exit(0);
}

vector<Rect> filter(vector<Rect> rects, Point p, Point q) {
	vector<Rect> res;
	for (auto r : rects) {
		if (!inside(p, r) && !inside(q, r)) {
			res.push_back(r);
		}
	}
	return res;
}

void solve(const vector<Rect> &rects, const vector<Point> &pts) {
	if ((int)pts.size() == k) {
		if (rects.empty()) {
			output(pts);
		}

		return;
	}

	Rect intersection;
	for (const auto &rect : rects) {
		self_intersect(intersection, rect);
	}

	for (int x : {intersection.x.l, intersection.x.r}) {
		for (int y : {intersection.y.l, intersection.y.r}) {
			Point p = {x, y};
			
			auto npts = pts;
			npts.push_back(p);
			
			vector<Rect> nrects;
			for (const auto &rect : rects) {
				if (!inside(p, rect)) {
					nrects.push_back(rect);
				}
			}

			solve(nrects, npts);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n >> k;
	vector<Rect> rects(n);
	for (auto &r : rects) {
		cin >> r;
	}

	vals.push_back(0);
	vals.push_back(INF + 1);
	for (const auto &r : rects) {
		vals.push_back(r.x.l);
		vals.push_back(r.x.r);
		vals.push_back(r.y.l);
		vals.push_back(r.y.r);
	}
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	while (vals.size() <= N) {
		vals.back() = INF;
		vals.push_back(INF + 1);
	}

	for (auto &r : rects) {
		adjust(r.x.l);
		adjust(r.y.l);
		adjust(r.x.r);
		adjust(r.y.r);
	}

	solve(rects, vector<Point>{});

	Rect intersection;
	for (const auto &r : rects) {
		self_intersect(intersection, r);
	}

	int dy = intersection.y.r, uy = intersection.y.l;
	int lx = intersection.x.r, rx = intersection.x.l;

	Seg base_sd = {lx + 1, rx - 1}, base_su = {lx + 1, rx - 1};
	Seg base_sl = {dy + 1, uy - 1}, base_sr = {dy + 1, uy - 1};

	vector<Seg> pref_dl(N + 1);
	vector<Seg> suff_dr(N + 1);
	vector<Seg> pref_du(N + 1);
	vector<Seg> suff_du(N + 1);
	vector<Seg> pref_lr(N + 1);
	vector<Seg> suff_lr(N + 1);
	vector<Seg> suff_lu(N + 1);
	vector<Seg> suff_ru(N + 1);

	for (const auto &r : rects) {
		int fd = inside(dy, r.y);
		int fu = inside(uy, r.y);
		int fl = inside(lx, r.x);
		int fr = inside(rx, r.x);
		
		if (fd + fu + fl + fr > 2) {
			continue;
		}

		if (fd + fu + fl + fr == 0) {
			assert(0);
		}

		if (fd + fu + fl + fr == 1) {
			if (fd) {
				self_intersect(base_sd, r.x);
			} else if (fu) {
				self_intersect(base_su, r.x);
			} else if (fl) {
				self_intersect(base_sl, r.y);
			} else {
				self_intersect(base_sr, r.y);
			}
		} else {
			if (fd && fu) {
				self_intersect(pref_du[r.x.r], r.x);
				self_intersect(suff_du[r.x.l], r.x);
			} else if (fd && fl) {
				self_intersect(pref_dl[r.x.r], r.y);
			} else if (fd && fr) {
				self_intersect(suff_dr[r.x.l], r.y);
			} else if (fl && fr) {
				self_intersect(pref_lr[r.y.r], r.y);
				self_intersect(suff_lr[r.y.l], r.y);
			} else if (fu && fl) {
				self_intersect(suff_lu[r.y.l], r.x);
			} else {
				self_intersect(suff_ru[r.y.l], r.x);
			}
		}
	}

	for (int i = 0; i < N; ++i) {
		self_intersect(pref_lr[i + 1], pref_lr[i]);
		self_intersect(pref_dl[i + 1], pref_dl[i]);
		self_intersect(pref_du[i + 1], pref_du[i]);
	}
	for (int i = N; i > 0; --i) {
		self_intersect(suff_dr[i - 1], suff_dr[i]);
		self_intersect(suff_du[i - 1], suff_du[i]);
		self_intersect(suff_lu[i - 1], suff_lu[i]);
		self_intersect(suff_ru[i - 1], suff_ru[i]);
		self_intersect(suff_lr[i - 1], suff_lr[i]);
	}

	for (int dx = base_sd.l; dx <= base_sd.r; ++dx) {
		Seg su = base_su, sl = base_sl, sr = base_sr;

		self_intersect(sl, pref_dl[dx - 1]);
		self_intersect(sr, suff_dr[dx + 1]);
		self_intersect(su, pref_du[dx - 1]);
		self_intersect(su, suff_du[dx + 1]);

		int ly = intersect(sl, pref_lr[N]).r;

		if (!inside(ly, sl)) {
			continue;
		}

		self_intersect(sr, pref_lr[ly - 1]);
		self_intersect(sr, suff_lr[ly + 1]);

		if (sr.l > sr.r) {
			continue;
		}

		int ry = sr.r;

		self_intersect(su, suff_lu[ly + 1]);
		self_intersect(su, suff_ru[ry + 1]);

		if (su.l > su.r) {
			continue;
		}

		int ux = su.l;

		output(vector<Point>{Point{dx, dy}, Point{lx, ly}, Point{rx, ry}, Point{ux, uy}});
	}

	for (int dx = base_sd.l; dx <= base_sd.r; ++dx) {
		Seg su = base_su, sl = base_sl, sr = base_sr;
			
		self_intersect(sl, pref_dl[dx - 1]);
		self_intersect(sr, suff_dr[dx + 1]);
		self_intersect(su, pref_du[dx - 1]);
		self_intersect(su, suff_du[dx + 1]);

		int ry = intersect(sr, pref_lr[N]).r;
		
		if (!inside(ry, sr)) {
			continue;
		}

		self_intersect(sl, pref_lr[ry - 1]);
		self_intersect(sl, suff_lr[ry + 1]);

		if (sl.l > sl.r) {
			continue;
		}

		int ly = sl.r;

		self_intersect(su, suff_lu[ly + 1]);
		self_intersect(su, suff_ru[ry + 1]);

		if (su.l > su.r) {
			continue;
		}

		int ux = su.l;
		
		output(vector<Point>{Point{dx, dy}, Point{lx, ly}, Point{rx, ry}, Point{ux, uy}});
	}


	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4664 KB Output is correct
2 Correct 6 ms 4672 KB Output is correct
3 Correct 6 ms 4636 KB Output is correct
4 Correct 6 ms 4672 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4564 KB Output is correct
2 Correct 6 ms 4672 KB Output is correct
3 Correct 6 ms 4672 KB Output is correct
4 Correct 6 ms 4632 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4664 KB Output is correct
2 Correct 6 ms 4672 KB Output is correct
3 Correct 6 ms 4672 KB Output is correct
4 Correct 6 ms 4668 KB Output is correct
5 Correct 6 ms 4672 KB Output is correct
6 Correct 6 ms 4672 KB Output is correct
7 Correct 7 ms 4672 KB Output is correct
8 Correct 7 ms 4672 KB Output is correct
9 Correct 7 ms 4672 KB Output is correct
10 Correct 6 ms 4672 KB Output is correct
11 Correct 7 ms 4552 KB Output is correct
12 Correct 6 ms 4672 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4588 KB Output is correct
2 Correct 5 ms 4672 KB Output is correct
3 Correct 6 ms 4672 KB Output is correct
4 Correct 6 ms 4672 KB Output is correct
5 Correct 6 ms 4672 KB Output is correct
6 Correct 6 ms 4672 KB Output is correct
7 Correct 6 ms 4672 KB Output is correct
8 Correct 10 ms 4672 KB Output is correct
9 Correct 6 ms 4676 KB Output is correct
10 Correct 8 ms 4672 KB Output is correct
11 Correct 8 ms 4672 KB Output is correct
12 Correct 6 ms 4672 KB Output is correct
13 Correct 8 ms 4672 KB Output is correct
14 Correct 46 ms 53824 KB Output is correct
15 Correct 6 ms 4672 KB Output is correct
16 Correct 6 ms 4660 KB Output is correct
17 Correct 44 ms 53788 KB Output is correct
18 Correct 7 ms 4672 KB Output is correct
19 Correct 6 ms 4672 KB Output is correct
20 Correct 44 ms 53844 KB Output is correct
21 Correct 6 ms 4672 KB Output is correct
22 Correct 6 ms 4672 KB Output is correct
23 Correct 45 ms 53732 KB Output is correct
24 Correct 7 ms 4628 KB Output is correct
25 Correct 8 ms 4672 KB Output is correct
26 Correct 8 ms 4672 KB Output is correct
27 Correct 7 ms 4672 KB Output is correct
28 Correct 7 ms 4664 KB Output is correct
29 Correct 7 ms 4648 KB Output is correct
30 Correct 6 ms 4664 KB Output is correct
31 Correct 44 ms 53820 KB Output is correct
32 Correct 43 ms 53836 KB Output is correct
33 Correct 45 ms 53832 KB Output is correct
34 Correct 43 ms 53812 KB Output is correct
35 Correct 51 ms 53844 KB Output is correct
36 Correct 47 ms 53764 KB Output is correct
37 Correct 45 ms 53828 KB Output is correct
38 Correct 46 ms 53820 KB Output is correct
39 Correct 45 ms 53844 KB Output is correct
40 Correct 47 ms 53808 KB Output is correct
41 Correct 51 ms 53904 KB Output is correct
42 Correct 51 ms 53804 KB Output is correct
43 Correct 44 ms 53768 KB Output is correct
44 Correct 44 ms 53876 KB Output is correct
45 Correct 8 ms 4672 KB Output is correct
46 Correct 45 ms 53804 KB Output is correct
47 Correct 43 ms 53876 KB Output is correct
48 Correct 46 ms 53768 KB Output is correct
49 Correct 44 ms 53808 KB Output is correct
50 Correct 44 ms 53832 KB Output is correct
51 Correct 45 ms 53776 KB Output is correct
52 Correct 45 ms 53820 KB Output is correct
53 Correct 44 ms 53780 KB Output is correct
54 Correct 46 ms 53800 KB Output is correct
55 Correct 43 ms 53684 KB Output is correct
56 Correct 42 ms 53684 KB Output is correct
57 Correct 43 ms 53692 KB Output is correct
58 Correct 43 ms 53668 KB Output is correct

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4664 KB Output is correct
2 Correct 6 ms 4672 KB Output is correct
3 Correct 6 ms 4636 KB Output is correct
4 Correct 6 ms 4672 KB Output is correct
5 Correct 262 ms 8580 KB Output is correct
6 Correct 259 ms 8508 KB Output is correct
7 Correct 264 ms 8636 KB Output is correct
8 Correct 258 ms 8468 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4564 KB Output is correct
2 Correct 6 ms 4672 KB Output is correct
3 Correct 6 ms 4672 KB Output is correct
4 Correct 6 ms 4632 KB Output is correct
5 Correct 267 ms 11172 KB Output is correct
6 Correct 268 ms 13956 KB Output is correct
7 Correct 265 ms 10808 KB Output is correct
8 Correct 272 ms 15932 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4664 KB Output is correct
2 Correct 6 ms 4672 KB Output is correct
3 Correct 6 ms 4672 KB Output is correct
4 Correct 6 ms 4668 KB Output is correct
5 Correct 6 ms 4672 KB Output is correct
6 Correct 6 ms 4672 KB Output is correct
7 Correct 7 ms 4672 KB Output is correct
8 Correct 7 ms 4672 KB Output is correct
9 Correct 7 ms 4672 KB Output is correct
10 Correct 6 ms 4672 KB Output is correct
11 Correct 7 ms 4552 KB Output is correct
12 Correct 6 ms 4672 KB Output is correct
13 Correct 268 ms 11832 KB Output is correct
14 Correct 269 ms 11316 KB Output is correct
15 Correct 268 ms 12216 KB Output is correct
16 Correct 265 ms 10548 KB Output is correct
17 Correct 279 ms 11320 KB Output is correct
18 Correct 261 ms 9520 KB Output is correct
19 Correct 272 ms 13748 KB Output is correct
20 Correct 355 ms 18964 KB Output is correct
21 Correct 271 ms 13712 KB Output is correct
22 Correct 286 ms 18644 KB Output is correct
23 Correct 318 ms 18520 KB Output is correct
24 Correct 322 ms 18072 KB Output is correct

Subtask #8
79.0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4588 KB Output is correct
2 Correct 5 ms 4672 KB Output is correct
3 Correct 6 ms 4672 KB Output is correct
4 Correct 6 ms 4672 KB Output is correct
5 Correct 6 ms 4672 KB Output is correct
6 Correct 6 ms 4672 KB Output is correct
7 Correct 6 ms 4672 KB Output is correct
8 Correct 10 ms 4672 KB Output is correct
9 Correct 6 ms 4676 KB Output is correct
10 Correct 8 ms 4672 KB Output is correct
11 Correct 8 ms 4672 KB Output is correct
12 Correct 6 ms 4672 KB Output is correct
13 Correct 8 ms 4672 KB Output is correct
14 Correct 46 ms 53824 KB Output is correct
15 Correct 6 ms 4672 KB Output is correct
16 Correct 6 ms 4660 KB Output is correct
17 Correct 44 ms 53788 KB Output is correct
18 Correct 7 ms 4672 KB Output is correct
19 Correct 6 ms 4672 KB Output is correct
20 Correct 44 ms 53844 KB Output is correct
21 Correct 6 ms 4672 KB Output is correct
22 Correct 6 ms 4672 KB Output is correct
23 Correct 45 ms 53732 KB Output is correct
24 Correct 7 ms 4628 KB Output is correct
25 Correct 8 ms 4672 KB Output is correct
26 Correct 8 ms 4672 KB Output is correct
27 Correct 7 ms 4672 KB Output is correct
28 Correct 7 ms 4664 KB Output is correct
29 Correct 7 ms 4648 KB Output is correct
30 Correct 6 ms 4664 KB Output is correct
31 Correct 44 ms 53820 KB Output is correct
32 Correct 43 ms 53836 KB Output is correct
33 Correct 45 ms 53832 KB Output is correct
34 Correct 43 ms 53812 KB Output is correct
35 Correct 51 ms 53844 KB Output is correct
36 Correct 47 ms 53764 KB Output is correct
37 Correct 45 ms 53828 KB Output is correct
38 Correct 46 ms 53820 KB Output is correct
39 Correct 45 ms 53844 KB Output is correct
40 Correct 47 ms 53808 KB Output is correct
41 Correct 51 ms 53904 KB Output is correct
42 Correct 51 ms 53804 KB Output is correct
43 Correct 44 ms 53768 KB Output is correct
44 Correct 44 ms 53876 KB Output is correct
45 Correct 8 ms 4672 KB Output is correct
46 Correct 45 ms 53804 KB Output is correct
47 Correct 43 ms 53876 KB Output is correct
48 Correct 46 ms 53768 KB Output is correct
49 Correct 44 ms 53808 KB Output is correct
50 Correct 44 ms 53832 KB Output is correct
51 Correct 45 ms 53776 KB Output is correct
52 Correct 45 ms 53820 KB Output is correct
53 Correct 44 ms 53780 KB Output is correct
54 Correct 46 ms 53800 KB Output is correct
55 Correct 43 ms 53684 KB Output is correct
56 Correct 42 ms 53684 KB Output is correct
57 Correct 43 ms 53692 KB Output is correct
58 Correct 43 ms 53668 KB Output is correct
59 Correct 268 ms 13368 KB Output is correct
60 Correct 267 ms 13376 KB Output is correct
61 Correct 264 ms 13464 KB Output is correct
62 Correct 273 ms 12856 KB Output is correct
63 Correct 261 ms 12340 KB Output is correct
64 Correct 263 ms 8692 KB Output is correct
65 Correct 277 ms 13268 KB Output is correct
66 Correct 455 ms 21992 KB Output is correct
67 Correct 317 ms 18112 KB Output is correct
68 Correct 578 ms 22996 KB Output is correct
69 Correct 697 ms 23364 KB Output is correct
70 Correct 496 ms 22788 KB Output is correct
71 Correct 275 ms 14068 KB Output is correct
72 Correct 689 ms 57520 KB Output is correct
73 Correct 291 ms 16384 KB Output is correct
74 Correct 394 ms 22376 KB Output is correct
75 Correct 487 ms 60968 KB Output is correct
76 Correct 413 ms 21856 KB Output is correct
77 Correct 302 ms 13864 KB Output is correct
78 Correct 803 ms 57416 KB Output is correct
79 Correct 313 ms 16952 KB Output is correct
80 Correct 343 ms 17876 KB Output is correct
81 Correct 684 ms 57436 KB Output is correct
82 Correct 368 ms 20944 KB Output is correct
83 Correct 421 ms 20916 KB Output is correct
84 Correct 451 ms 22076 KB Output is correct
85 Correct 573 ms 23468 KB Output is correct
86 Correct 328 ms 17916 KB Output is correct
87 Correct 619 ms 23088 KB Output is correct
88 Correct 441 ms 22876 KB Output is correct
89 Correct 554 ms 61272 KB Output is correct
90 Correct 740 ms 57356 KB Output is correct
91 Correct 542 ms 60932 KB Output is correct
92 Correct 777 ms 61372 KB Output is correct
93 Correct 639 ms 57312 KB Output is correct
94 Correct 712 ms 57544 KB Output is correct
95 Correct 697 ms 57572 KB Output is correct
96 Correct 591 ms 57304 KB Output is correct
97 Correct 654 ms 57480 KB Output is correct
98 Correct 614 ms 57328 KB Output is correct
99 Correct 532 ms 57336 KB Output is correct
100 Correct 737 ms 57504 KB Output is correct
101 Correct 695 ms 57164 KB Output is correct
102 Correct 490 ms 60892 KB Output is correct
103 Correct 821 ms 57156 KB Output is correct
104 Correct 510 ms 61328 KB Output is correct
105 Correct 768 ms 57324 KB Output is correct
106 Correct 720 ms 61356 KB Output is correct
107 Correct 621 ms 57104 KB Output is correct
108 Correct 763 ms 61140 KB Output is correct
109 Correct 742 ms 57020 KB Output is correct
110 Correct 653 ms 57024 KB Output is correct
111 Correct 619 ms 57208 KB Output is correct
112 Correct 762 ms 64596 KB Output is correct
113 Correct 462 ms 64564 KB Output is correct
114 Correct 456 ms 64768 KB Output is correct
115 Correct 460 ms 64564 KB Output is correct
116 Correct 453 ms 64480 KB Output is correct
117 Correct 430 ms 64744 KB Output is correct
118 Correct 429 ms 64632 KB Output is correct
119 Correct 430 ms 64544 KB Output is correct
120 Correct 436 ms 64672 KB Output is correct
121 Correct 444 ms 64636 KB Output is correct
122 Correct 437 ms 64712 KB Output is correct
123 Correct 437 ms 64704 KB Output is correct
124 Correct 435 ms 64688 KB Output is correct
125 Correct 464 ms 64564 KB Output is correct
126 Correct 444 ms 64588 KB Output is correct