Submission #217449

#	Time	Username	Problem	Language	Result	Execution time	Memory
217449		Toadologist	Hamburg Steak (JOI20_hamburg)	C++11	100 / 100	696 ms	92100 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }
template<typename A, typename B>
ostream& operator << (ostream& out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}

const int maxN = 200000 + 5;
struct Rect {
	int L, D, R, U;
	Rect() {}
	Rect(int l, int d, int r, int u) : L(l), D(d), R(r), U(u) {}
	LL area() const {
		return (LL)max(0, R - L + 1) * (LL)max(0, U - D + 1);
	}
	bool hit(pii p) const {
		return L <= p.first && p.first <= R && D <= p.second && p.second <= U;
	}
};
int nx, ny;
vector<int> tx, ty;

Rect com(Rect x, Rect y) {
	return Rect(max(x.L, y.L), max(x.D, y.D), min(x.R, y.R), min(x.U, y.U));
}

void disc(vector<Rect> &v) {
	{
	vector<int> &t = tx;
	t.clear();
	for(auto r : v) t.push_back(r.L), t.push_back(r.R);
	sort(t.begin(), t.end());
//	t.erase(unique(t.begin(), t.end()), t.end());
	vector<int> c(2 * v.size(), 0);
	for(auto &r : v) {
		int i = lower_bound(t.begin(), t.end(), r.L) - t.begin();
		r.L = i + ++c[i];
	}
	for(auto &r : v) {
		int i = lower_bound(t.begin(), t.end(), r.R) - t.begin();
		r.R = i + ++c[i];
	}
	nx = t.size();
	}
	{
	vector<int> &t = ty;
	t.clear();
	for(auto r : v) t.push_back(r.D), t.push_back(r.U);
	sort(t.begin(), t.end());
//	t.erase(unique(t.begin(), t.end()), t.end());
	vector<int> c(2 * v.size(), 0);
	for(auto &r : v) {
		int i = lower_bound(t.begin(), t.end(), r.D) - t.begin();
		r.D = i + ++c[i];
	}
	for(auto &r : v) {
		int i = lower_bound(t.begin(), t.end(), r.U) - t.begin();
		r.U = i + ++c[i];
	}
	ny = t.size();
	}
	
	assert(nx == ny);
}

vector<Rect> ans;

vector<int> oned(vector<pii> &v) {
	displayv(v);
	vector<int> res;
	sort(v.begin(), v.end());
	int last = max(nx, ny) + 1;
	for(int i = (int)v.size() - 1; i >= 0; --i) {
		if(v[i].first <= last && last <= v[i].second) continue;
		else res.push_back(last = v[i].first);
	}
	displayv(res);
	return res;
}

struct Segt { // i = L
#define lson (o*2)
#define rson (lson | 1)
	int n;
	Rect ext[maxN * 8];
	Segt() {}
	void clear(int n) {
		this->n = n;
		for(int i = 0; i <= 4 * n; ++i)
			ext[i] = Rect(1, 1, n, n);
	}
	void insert(int o, int L, int R, Rect r) {
		if(L == R) {
			ext[o] = r;
		} else {
			int M = (L + R) >> 1;
			if(r.L <= M) insert(lson, L, M, r);
			else insert(rson, M + 1, R, r);
			ext[o] = com(ext[lson], ext[rson]);
		}
	}
	void erase(int o, int L, int R, Rect r) {
		if(L == R) {
			ext[o] = Rect(1, 1, n, n);
		} else {
			int M = (L + R) >> 1;
			if(r.L <= M) erase(lson, L, M, r);
			else erase(rson, M + 1, R, r);
			ext[o] = com(ext[lson], ext[rson]);
		}
	}
	Rect query(int o, int L, int R, int ql, int qr) {
		if(ql <= L && R <= qr) {
			return ext[o];
		} else {
			int M = (L + R) >> 1;
			Rect r(1, 1, n, n);
			if(ql <= M) r = com(r, query(lson, L, M, ql, qr));
			if(qr > M) r = com(r, query(rson, M + 1, R, ql, qr));
			return r;
		}
	}
#undef lson
#undef rson
} up, down, both;

bool solve(vector<Rect> &v, int k, vector<pii> &res) {
	res.clear();
	{ // k == 0
		if(v.size() == 0) return true;
		if(k <= 0) return false;
	}
	
	Rect c(1, 1, nx, ny);
	for(auto r : v) c = com(c, r);
	{ // k == 1
		if(c.area() > 0) {
			res.emplace_back(c.L, c.D);
			return true;
		}
		if(k <= 1) return false;
	}
	if(c.L <= c.R) {
		vector<pii> segs;
		for(int i = 0; i < (int)v.size(); ++i)
			segs.emplace_back(v[i].D, v[i].U);
		vector<int> pos = oned(segs);
		if((int)pos.size() > k) return false;
		
		for(auto p : pos) res.emplace_back(c.L, p);
		return true;
	}
	if(c.D <= c.U) {
		vector<pii> segs;
		for(int i = 0; i < (int)v.size(); ++i)
			segs.emplace_back(v[i].L, v[i].R);
		vector<int> pos = oned(segs);
		if((int)pos.size() > k) return false;
		
		for(auto p : pos) res.emplace_back(p, c.D);
		return true;
	}
	{ // k == 2
		auto check = [&](pii x, pii y) {
			for(auto r : v) {
				if(!r.hit(x) && !r.hit(y)) {
					return false;
				}
			}
			res.push_back(x);
			res.push_back(y);
			return true;
		};
		if(check(pii(c.L, c.D), pii(c.R, c.U))) return true;
		if(check(pii(c.L, c.U), pii(c.R, c.D))) return true;
		if(k <= 2) return false;
	}
	{ // k == 3
		auto check = [&](pii x) {
			vector<Rect> nv;
			vector<pii> sol;
			for(auto r : v) {
				if(!r.hit(x)) nv.push_back(r);
			}
			if(solve(nv, k - 1, sol)) {
				res.push_back(x);
				res.insert(res.end(), sol.begin(), sol.end());
				return true;
			}
			return false;
		};
		if(check(pii(c.L, c.D))) return true;
		if(check(pii(c.L, c.U))) return true;
		if(check(pii(c.R, c.D))) return true;
		if(check(pii(c.R, c.U))) return true;
		if(k <= 3) return false;
	}
	{
		// c.R ~ c.L; c.U ~ c.D
		int L = c.R, R = c.L, D = c.U, U = c.D;
		eprintf("heart %d %d %d %d\n", tx[L - 1], ty[D - 1], tx[R - 1], ty[U - 1]);
		set<int> us, ds;
		vector<pii> es; // (y, i)
		pii llim(1, ny);
		
		auto add = [&](Rect r, int coef) {
			
			assert(coef == 1 || coef == -1);
			Rect CL, CR, CD, CU;
			pii p;
			CL = com(Rect(L, D, L, U), r);
			CR = com(Rect(R, D, R, U), r);
			CD = com(Rect(L, D, R, D), r);
			CU = com(Rect(L, U, R, U), r);
			assert(CL.area() > 0);
			if(CR.area()) {
				if(coef == 1) ds.insert(r.D), us.insert(r.U);
				else ds.erase(r.D), us.erase(r.U);
			} else if(CU.area()) {
				if(coef == 1) up.insert(1, 1, nx, r);
				else up.erase(1, 1, nx, r);
			} else {
				if(coef == 1) down.insert(1, 1, nx, r);
				else down.erase(1, 1, nx, r);
			}
		};
		
		for(int i = 0; i < (int)v.size(); ++i) {
			Rect CL, CR, CD, CU;
			pii p;
			CL = com(Rect(L, D, L, U), v[i]);
			CR = com(Rect(R, D, R, U), v[i]);
			CD = com(Rect(L, D, R, D), v[i]);
			CU = com(Rect(L, U, R, U), v[i]);
//			if(tx[v[i].R - 1] == 556967885) {
//				eprintf("got = %d %d %d %d\n", tx[v[i].L - 1], ty[v[i].D - 1], tx[v[i].R - 1], ty[v[i].U - 1]);
//				eprintf("%lld %lld %lld %lld\n", CL.area(), CR.area(), CD.area(), CU.area());
//			}
			int adj = !!CL.area() + !!CR.area() + !!CD.area() + !!CU.area();
			assert(adj > 0);
			if(adj >= 3) continue;
			if(adj == 1) {
				if(CL.area()) chmax(llim.first, CL.D), chmin(llim.second, CL.U);
				else if(CR.area()) ds.insert(CL.D), us.insert(CL.U);
				else if(CD.area()) down.insert(1, 1, nx, v[i]);
				else if(CU.area()) up.insert(1, 1, nx, v[i]);
			} else {
				if(CL.area()) add(v[i], 1), es.emplace_back(CL.D, -i-1), es.emplace_back(CL.U + 1, i);
				else {
					if(CU.area() && CD.area()) both.insert(1, 1, nx, v[i]);
					else if(CU.area()) up.insert(1, 1, nx, v[i]);
					else if(CD.area()) down.insert(1, 1, nx, v[i]);
				}
			}
		}
//		eprintf("llim = [%d %d]\n", ty[llim.first - 1], ty[llim.second - 1]);
		es.emplace_back(llim.first, maxN);
		es.emplace_back(llim.second, maxN);
		sort(es.begin(), es.end());
		for(int i = 0; i < (int)es.size(); ++i) {
			int id = es[i].second;
			if(id < 0) add(v[-id-1], -1);
			else if(id != maxN) add(v[id], 1);
			else {}
			
			if((i + 1 == (int)es.size() || es[i + 1].first != es[i].first)
				&& llim.first <= es[i].first && es[i].first <= llim.second) {
//				eprintf("L picks %d\n", ty[es[i].first - 1]);
				// case 1: U <= D
				{
					Rect u = com(up.query(1, 1, nx, 1, nx), both.query(1, 1, nx, 1, nx));
					Rect d = down.query(1, 1, nx, 1, nx);
					if(d.R < u.R) goto NEXT;
					if(u.R + 1 <= nx) d = com(d, both.query(1, 1, nx, u.R + 1, nx));
					
					Rect rest(R, D, R, U);
					if(ds.size()) chmax(rest.D, *ds.rbegin());
					if(us.size()) chmin(rest.U, *us.begin());
					if(u.R + 1 <= nx) rest = com(rest, up.query(1, 1, nx, u.R + 1, nx));
					if(d.R + 1 <= ny) rest = com(rest, down.query(1, 1, nx, d.R + 1, nx)), rest = com(rest, both.query(1, 1, nx, d.R + 1, nx));
//					eprintf("U picks %d, D picks %d\n", tx[u.R - 1], tx[d.R - 1]);
//					eprintf("rest = %d %d %d %d\n", tx[rest.L - 1], ty[rest.D - 1], tx[rest.R - 1], ty[rest.U - 1]);
					if(rest.area() > 0) {
						res.emplace_back(L, es[i].first);
						res.emplace_back(u.R, U);
						res.emplace_back(d.R, D);
						res.emplace_back(rest.L, rest.D);
						return true;
					}
				}
				NEXT:
				// case 2: D <= U
				{
					Rect d = com(down.query(1, 1, nx, 1, nx), both.query(1, 1, nx, 1, nx));
					Rect u = up.query(1, 1, nx, 1, nx);
//					eprintf("U picks %d, D picks %d\n", tx[u.R - 1], tx[d.R - 1]);
					if(u.R < d.R) continue;
					if(d.R + 1 <= nx) u = com(u, both.query(1, 1, nx, d.R + 1, nx));
					
					Rect rest(R, D, R, U);
					if(ds.size()) chmax(rest.D, *ds.rbegin());
					if(us.size()) chmin(rest.U, *us.begin());
					if(d.R + 1 <= nx) rest = com(rest, down.query(1, 1, nx, d.R + 1, nx));
					if(u.R + 1 <= ny) rest = com(rest, up.query(1, 1, nx, u.R + 1, nx)), rest = com(rest, both.query(1, 1, nx, u.R + 1, nx));
//					eprintf("U picks %d, D picks %d\n", tx[u.R - 1], tx[d.R - 1]);
//					eprintf("rest = %d %d %d %d\n", tx[rest.L - 1], ty[rest.D - 1], tx[rest.R - 1], ty[rest.U - 1]);
					if(rest.area() > 0) {
						res.emplace_back(L, es[i].first);
						res.emplace_back(d.R, D);
						res.emplace_back(u.R, U);
						res.emplace_back(rest.L, rest.D);
						return true;
					}
				}
			}
		}
		
		if(k <= 4) return false;
	}
	return false;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
#endif
	int n, k;
	cin >> n >> k;
	vector<Rect> v;
	for(int i = 0; i < n; ++i) {
		int l, d, r, u;
		cin >> l >> d >> r >> u;
		v.emplace_back(l, d, r, u);
	}
	disc(v);
	for(auto r : v) eprintf("rect %d %d %d %d\n", r.L, r.D, r.R, r.U);
	
	down.clear(2 * n);
	up.clear(2 * n);
	both.clear(2 * n);
	
	vector<pii> res;
	bool ok = solve(v, k, res);
	assert(ok);
	while((int)res.size() < k) res.emplace_back(1, 1);
	for(auto p : res) cout << tx[p.first - 1] << " " << ty[p.second - 1] << endl;
	return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:357:11: warning: variable 'r' set but not used [-Wunused-but-set-variable]
  357 |  for(auto r : v) eprintf("rect %d %d %d %d\n", r.L, r.D, r.R, r.U);
      |           ^

• 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