Submission #308286

#	Time	Username	Problem	Language	Result	Execution time	Memory
308286		cki86201	Hamburg Steak (JOI20_hamburg)	C++17	100 / 100	640 ms	47860 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;

#define Fi first
#define Se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;

const int INF = 1e9 + 10, M = 4e5 + 5;
pii operator+(pii a, pii b) { return {max(a.Fi, b.Fi), min(a.Se, b.Se)}; }
int N, K;
vector <int> vx, vy;
struct rect {
	int x1, y1, x2, y2;
	bool In(int x, int y) {
		return x1 <= x && x <= x2 && y1 <= y && y <= y2;
	}
} R[200020];

void trial(vector <pii> ans, int flp = 0) {
	if(szz(ans) == 0 || szz(ans) > K) return;
	while(szz(ans) < K) ans.pb(ans[0]);
	for(int i=1;i<=N;i++) {
		int r = 0;
		for(auto &[x, y] : ans) if(R[i].In(x, y)) {
			r = 1; break;
		}
		if(r == 0) return;
	}
	for(auto [x, y] : ans) {
		if(flp) y = szz(vy) + 1 - y;
		printf("%d %d\n", vx[x-1], vy[y-1]);
	}
	exit(0);
}

int arr[4*M+5];
vector <int> solve_linear(vector <pii> R) {
	for(int i=1;i<=M;i++) arr[i] = INF;
	for(auto [x, y] : R) arr[x] = min(arr[x], y);
	for(int i=M-1;i;i--) arr[i] = min(arr[i], arr[i+1]);
	vector <int> res;
	for(int t=1;arr[t]!=INF;t=arr[t]+1) res.pb(arr[t]);
	return res;
}

pii seg[6][2][M+5];

void solve(vector <int> rst, int k, vector <pii> ans) {
	if(szz(rst) == 0) trial(ans);
	if(k == 0) return;
	int lx = INF, rx = -INF, ly = INF, ry = -INF;
	for(int i : rst) {
		lx = min(lx, R[i].x2);
		rx = max(rx, R[i].x1);
		ly = min(ly, R[i].y2);
		ry = max(ry, R[i].y1);
	}
	if(k == 1) {
		if(lx >= rx && ly >= ry) {
			ans.pb({rx, ry});
			trial(ans);
		}
		return;
	}
	if(lx >= rx) {
		vector <pii> V;
		for(int i : rst) V.pb({R[i].y1, R[i].y2});
		auto ys = solve_linear(V);
		for(int y : ys) ans.pb({rx, y});
		trial(ans);
		return;
	}
	if(ly >= ry) {
		vector <pii> V;
		for(int i : rst) V.pb({R[i].x1, R[i].x2});
		auto xs = solve_linear(V);
		for(int x : xs) ans.pb({x, ry});
		trial(ans);
		return;
	}
	vector <pii> vert;
	for(int x : {lx, rx}) for(int y : {ly, ry}) vert.pb({x, y});
	for(auto [x, y] : vert) {
		vector <int> nst;
		for(int i : rst) if(!R[i].In(x, y)) nst.pb(i);
		auto ans2 = ans; ans2.pb({x, y});
		solve(nst, k - 1, ans2);
	}

	if(k != 4) return;
	auto fy = [&](int &y) { y = szz(vy) + 1 - y; };
	auto Intersect = [&](const rect &a, const rect &b) {
		pii x = pii(a.x1, a.x2) + pii(b.x1, b.x2);
		if(x.Fi > x.Se) return 0;
		pii y = pii(a.y1, a.y2) + pii(b.y1, b.y2);
		if(y.Fi > y.Se) return 0;
		return 1;
	};
	auto solve4 = [&](int flp) {
		rect Side[4];
		Side[0] = {lx, ly, lx, ry};
		Side[1] = {lx, ry, rx, ry};
		Side[2] = {rx, ly, rx, ry};
		Side[3] = {lx, ly, rx, ly};
		auto type = [&](int t) {
			int res = 0;
			rep(i, 4) if(Intersect(R[t], Side[i])) res |= 1<<i;
			return res;
		};
		pii Seg[4];
		Seg[0] = Seg[2] = {ly + 1, ry - 1};
		Seg[1] = Seg[3] = {lx + 1, rx - 1};
		auto upd = [&](pii &a, pii b) { a = a + b; };
		rep(i, 6) rep(j, 2) rep(k, M+1) seg[i][j][k] = pii(-INF, INF);
		int nrx = INF;
		for(int i=1;i<=N;i++) {
			int t = type(i);
			pii wx = {R[i].x1, R[i].x2}, wy = {R[i].y1, R[i].y2};
			if(t == 1) upd(Seg[0], wy);
			else if(t == 2) upd(Seg[1], wx);
			else if(t == 4) upd(Seg[2], wy);
			else if(t == 8) upd(Seg[3], wx);
			else if(t == 3) upd(seg[0][0][R[i].y1-1], wx);
			else if(t == 5) {
				upd(seg[1][0][R[i].y1-1], wy);
				upd(seg[1][1][R[i].y2+1], wy);
			}
			else if(t == 9) upd(seg[2][1][R[i].y2+1], wx);
			else if(t == 6) upd(seg[3][0][R[i].x1-1], wy);
			else if(t == 10) {
				upd(seg[4][0][R[i].x1-1], wx);
				upd(seg[4][1][R[i].x2+1], wx);
				nrx = min(nrx, R[i].x2);
			}
			else if(t == 12) upd(seg[5][1][R[i].y2+1], wx);
		}
		rep(i, 6) {
			for(int j=M-1;j;j--) upd(seg[i][0][j], seg[i][0][j+1]);
			for(int j=2;j<=M;j++) upd(seg[i][1][j], seg[i][1][j-1]);
			for(int j=1;j<=M;j++) upd(seg[i][0][j], seg[i][1][j]);
		}
		vector <pii> ans(4);
		for(int i=Seg[0].Fi;i<=Seg[0].Se;i++) {
			ans[0] = {lx, i};
			pii NS[3];
			rep(j, 3) NS[j] = Seg[j+1] + seg[j][0][i];
			int ri = min({nrx, NS[0].Se, NS[2].Se});
			if(NS[0].Fi > ri) continue;
			ans[1] = {ri, ry};
			upd(NS[1], seg[3][0][ri]);
			upd(NS[2], seg[4][0][ri]);
			if(NS[1].Fi > NS[1].Se) continue;
			int rj = NS[1].Fi;
			ans[2] = {rx, rj};
			upd(NS[2], seg[5][0][rj]);
			if(NS[2].Fi > NS[2].Se) continue;
			ans[3] = {NS[2].Se, ly};
			trial(ans, flp);
		}
	};

	solve4(0);
	for(int i=1;i<=N;i++) fy(R[i].y1), fy(R[i].y2), swap(R[i].y1, R[i].y2);
	swap(ly, ry); fy(ly), fy(ry);
	solve4(1);
}

int main() {
	scanf("%d%d", &N, &K);
	for(int i=1;i<=N;i++) {
		scanf("%d%d%d%d", &R[i].x1, &R[i].y1, &R[i].x2, &R[i].y2);
		vx.pb(R[i].x1), vx.pb(R[i].x2);
		vy.pb(R[i].y1), vy.pb(R[i].y2);
	}
	sort(all(vx)); vx.resize(unique(all(vx)) - vx.begin());
	sort(all(vy)); vy.resize(unique(all(vy)) - vy.begin());
	for(int i=1;i<=N;i++) {
		auto &[x1, y1, x2, y2] = R[i];
		x1 = (int)(lower_bound(all(vx), x1) - vx.begin()) + 1;
		y1 = (int)(lower_bound(all(vy), y1) - vy.begin()) + 1;
		x2 = (int)(lower_bound(all(vx), x2) - vx.begin()) + 1;
		y2 = (int)(lower_bound(all(vy), y2) - vy.begin()) + 1;
	}
	vector <int> rst;
	for(int i=1;i<=N;i++) rst.pb(i);
	solve(rst, K, {});
	return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:176:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  176 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:178:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  178 |   scanf("%d%d%d%d", &R[i].x1, &R[i].y1, &R[i].x2, &R[i].y2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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