제출 #1002750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002750		PagodePaiva	Izvanzemaljci (COI21_izvanzemaljci)	C++17	0 / 100	1 ms	348 KiB

izvanzemaljci

#include<bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

struct Ret{
	int minx, miny, maxx, maxy;
	vector <array <int, 4>> history;
	Ret(){
		minx = 1e12, maxx = -1e12, miny = 1e12, maxy = -1e12;
	}
	void add(pair <int, int> p){
		history.push_back({minx, maxx, miny, maxy});
		minx = min(minx, p.first);
		maxx = max(maxx, p.first);
		miny = min(miny, p.second);
		maxy = max(maxy, p.second);
		return;
	}
	void rollback(){
		minx = history.back()[0];
		maxx = history.back()[1];
		miny = history.back()[2];
		maxy = history.back()[3];
		history.pop_back();
	}
	array <int, 3> query(){
		return {max({1LL, abs(maxx-minx), abs(maxy-miny)}), minx, miny};
	}
	void clear(){
		history.clear();
		minx = 1e12, maxx = -1e12, miny = 1e12, maxy = -1e12;
	}
} x1, x2;

int32_t main(){
	int n, k;
	cin >> n >> k;
	vector <pair <int, int>> v;
	for(int i = 0;i < n;i++){
		int a, b;
		cin >> a >> b;
		v.push_back({a, b});
	}
	int minx = 1e12, maxx = -1e12, miny = 1e12, maxy = -1e12;
	for(auto x : v){
		minx = min(x.first, minx);
		maxx = max(x.first, maxx);
		miny = min(x.second, miny);
		maxy = max(x.second, maxy);
	}
	sort(v.begin(), v.end()); 
	for(int i = v.size()-1;i >= 0;i--){
		x2.add(v[i]);
	}
	array <int, 3> res1 = {max({1LL, abs(maxx-minx), abs(maxy-miny)}), minx, miny}, res2 = {1, (int) 1e9, (int) 1e9};
	for(int i = 0;i < n-1;i++){
		x2.rollback();
		x1.add(v[i]);
		swap(v[i].first, v[i].second);
		if(max(x1.query()[0], x2.query()[0]) < max(res1[0], res2[0])){
			res1 = x1.query();
			res2 = x2.query();
		}
	}
	x1.clear();
	x2.clear();
	sort(v.begin(), v.end());
	for(int i = v.size()-1;i >= 0;i--){
		swap(v[i].first, v[i].second);
		x2.add(v[i]);
		//cout << x2.query()[0] << ' ';
	}
	//cout << endl;
	for(int i = 0;i < n-1;i++){
		x2.rollback();
		x1.add(v[i]);
		if(max(x1.query()[0], x2.query()[0]) < max(res1[0], res2[0])){
			res1 = x1.query();
			res2 = x2.query();
		}
	}
	cout << res1[1] << ' ' << res1[2] << ' ' << res1[0] << endl << res2[1] << ' ' << res2[2] << ' ' << res2[0] << endl;
}

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