oj.uz

Submission #308285

# Submission time Handle Problem Language Result Execution time Memory
308285 2020-09-30T19:46:09 Z cki86201 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 451 ms 38016 KB 
#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, ry};
		Seg[1] = Seg[3] = {lx, rx};
		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=ly+1;i<ry;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 > NS[0].Se) 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(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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 360 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 440 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2048 KB Output is correct
2 Correct 7 ms 2048 KB Output is correct
3 Correct 6 ms 2048 KB Output is correct
4 Correct 6 ms 2048 KB Output is correct
5 Correct 8 ms 1992 KB Output is correct
6 Correct 6 ms 2048 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2048 KB Output is correct
2 Correct 7 ms 2048 KB Output is correct
3 Correct 9 ms 2048 KB Output is correct
4 Correct 6 ms 2048 KB Output is correct
5 Correct 7 ms 2048 KB Output is correct
6 Correct 6 ms 2048 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Incorrect 85 ms 38016 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 360 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 362 ms 8412 KB Output is correct
6 Correct 404 ms 8396 KB Output is correct
7 Correct 367 ms 8516 KB Output is correct
8 Correct 451 ms 8396 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 440 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 374 ms 9040 KB Output is correct
6 Correct 369 ms 9048 KB Output is correct
7 Correct 365 ms 9060 KB Output is correct
8 Correct 398 ms 9936 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2048 KB Output is correct
2 Correct 7 ms 2048 KB Output is correct
3 Correct 6 ms 2048 KB Output is correct
4 Correct 6 ms 2048 KB Output is correct
5 Correct 8 ms 1992 KB Output is correct
6 Correct 6 ms 2048 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 383 ms 13524 KB Output is correct
14 Correct 397 ms 13532 KB Output is correct
15 Correct 439 ms 13420 KB Output is correct
16 Correct 377 ms 13516 KB Output is correct
17 Correct 368 ms 13520 KB Output is correct
18 Correct 370 ms 13412 KB Output is correct
19 Correct 387 ms 9672 KB Output is correct
20 Correct 368 ms 9996 KB Output is correct
21 Correct 436 ms 11588 KB Output is correct
22 Correct 380 ms 10364 KB Output is correct
23 Correct 382 ms 11308 KB Output is correct
24 Correct 389 ms 11480 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2048 KB Output is correct
2 Correct 7 ms 2048 KB Output is correct
3 Correct 9 ms 2048 KB Output is correct
4 Correct 6 ms 2048 KB Output is correct
5 Correct 7 ms 2048 KB Output is correct
6 Correct 6 ms 2048 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Incorrect 85 ms 38016 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -