Submission #484461

#	Time	Username	Problem	Language	Result	Execution time	Memory
484461		valerikk	Hamburg Steak (JOI20_hamburg)	C++17	100 / 100	821 ms	64768 KiB

hamburg

#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 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 6 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 79 / 79