Submission #420735

#	Time	Username	Problem	Language	Result	Execution time	Memory
420735		Berted	Izvanzemaljci (COI21_izvanzemaljci)	C++14	5 / 100	34 ms	460 KiB

izvanzemaljci

#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>
#define int long long
#define pii pair<int, int>
#define ppi pair<pii, int>
#define fst first
#define snd second

using namespace std;

const int INF = 1e9 + 7;

int N, K;
pii A[100001];

pii prefMin[100001], sufMin[100001];
pii prefMax[100001], sufMax[100001];
vector<ppi> ans;

inline bool comp(const pii &L, const pii &R) {return make_pair(L.snd, L.fst) < make_pair(R.snd, R.fst);}
inline void solve()
{
	for (int i = 0; i < N; i++)
	{
		prefMin[i] = A[i]; prefMax[i] = A[i];
		if (i) 
		{
			prefMin[i].fst = min(prefMin[i - 1].fst, prefMin[i].fst);
			prefMin[i].snd = min(prefMin[i - 1].snd, prefMin[i].snd);
			prefMax[i].fst = max(prefMax[i - 1].fst, prefMax[i].fst);
			prefMax[i].snd = max(prefMax[i - 1].snd, prefMax[i].snd);
		}
	}
	for (int i = N - 1; i >= 0; i--)
	{
		sufMin[i] = A[i]; sufMax[i] = A[i];
		if (i + 1 < N)
		{
			sufMin[i].fst = min(sufMin[i + 1].fst, sufMin[i].fst);
			sufMin[i].snd = min(sufMin[i + 1].snd, sufMin[i].snd);
			sufMax[i].fst = max(sufMax[i + 1].fst, sufMax[i].fst);
			sufMax[i].snd = max(sufMax[i + 1].snd, sufMax[i].snd);
		}
	}
	for (int i = 0; i + 1 < N; i++)
	{
		pii aL = prefMin[i], aR = prefMax[i], bL = sufMin[i + 1], bR = sufMax[i + 1];
		int sA = max(aR.fst - aL.fst, aR.snd - aL.snd);
		int sB = max(bR.fst - bL.fst, bR.snd - bL.snd);

		if (sA == 0) {sA = 1; aL.fst--; aL.snd--;}
		if (sB == 0) {sB = 1;}

		pii iL = {max(aL.fst, bL.fst), max(aL.snd, bL.snd)};
		pii iR = {min(aL.fst + sA, bL.fst + sB), min(aL.snd + sA, bL.snd + sB)};

		if (iL.fst <= iR.fst && iL.snd <= iR.snd) continue;

		if (sA > sB)
		{
			if (ans.size() && ans[0].snd <= sA) continue;
			ans.clear();
			ans.push_back({aL, sA}); ans.push_back({bL, sB});
		}
		else
		{
			if (ans.size() && ans[0].snd <= sB) continue;
			ans.clear();
			ans.push_back({bL, sB}); ans.push_back({aL, sA});
		}

	}
}

int32_t main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> K;
	if (K == 1)
	{
		int mnY = INF, mxY = -INF, mnX = INF, mxX = -INF;
		for (int i = 0; i < N; i++)
		{
			int x, y; cin >> x >> y;
			mnY = min(mnY, y); mxY = max(mxY, y);
			mnX = min(mnX, x); mxX = max(mxX, x);
		}
		cout << mnX << " " << mnY << " " << max(1LL, max(mxX - mnX, mxY - mnY)) << "\n";
	}
	else if (K == 2)
	{
		for (int i = 0; i < N; i++) {cin >> A[i].fst >> A[i].snd;}
		sort(A, A + N); solve();
		sort(A, A + N, comp); solve();

		//if (ans.size() < K) return 0;

		for (int i = 0; i < K; i++)
		{
			cout << ans[i].fst.fst << " " << ans[i].fst.snd << " " << ans[i].snd << "\n";
		}
	}
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 21
• Subtask 3: 0 / 12
• Subtask 4: 0 / 30
• Subtask 5: 0 / 32