oj.uz

Submission #308284

# Submission time Handle Problem Language Result Execution time Memory
308284 2020-09-30T19:39:36 Z cki86201 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 618 ms 38008 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);
			}
		}
		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);
		}
	};

	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:175:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  175 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:177:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  177 |   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 384 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 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2048 KB Output is correct
2 Correct 7 ms 2048 KB Output is correct
3 Correct 7 ms 2080 KB Output is correct
4 Correct 7 ms 2048 KB Output is correct
5 Correct 6 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 4 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2048 KB Output is correct
2 Correct 6 ms 2024 KB Output is correct
3 Correct 6 ms 2048 KB Output is correct
4 Correct 8 ms 2048 KB Output is correct
5 Correct 6 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 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Incorrect 93 ms 38008 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 384 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 375 ms 8356 KB Output is correct
6 Correct 386 ms 8384 KB Output is correct
7 Correct 392 ms 8412 KB Output is correct
8 Correct 370 ms 8404 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 392 ms 9048 KB Output is correct
6 Correct 376 ms 9028 KB Output is correct
7 Correct 420 ms 9024 KB Output is correct
8 Correct 400 ms 9952 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2048 KB Output is correct
2 Correct 7 ms 2048 KB Output is correct
3 Correct 7 ms 2080 KB Output is correct
4 Correct 7 ms 2048 KB Output is correct
5 Correct 6 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 4 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 391 ms 13400 KB Output is correct
14 Correct 378 ms 13392 KB Output is correct
15 Correct 418 ms 13508 KB Output is correct
16 Correct 379 ms 13396 KB Output is correct
17 Correct 377 ms 13392 KB Output is correct
18 Correct 367 ms 13508 KB Output is correct
19 Correct 367 ms 9688 KB Output is correct
20 Correct 381 ms 9868 KB Output is correct
21 Correct 401 ms 11568 KB Output is correct
22 Correct 421 ms 10432 KB Output is correct
23 Correct 383 ms 11220 KB Output is correct
24 Correct 618 ms 11456 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2048 KB Output is correct
2 Correct 6 ms 2024 KB Output is correct
3 Correct 6 ms 2048 KB Output is correct
4 Correct 8 ms 2048 KB Output is correct
5 Correct 6 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 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Incorrect 93 ms 38008 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -