oj.uz

Submission #1002776

# Submission time Handle Problem Language Result Execution time Memory
1002776 2024-06-19T19:32:32 Z PagodePaiva Izvanzemaljci (COI21_izvanzemaljci) C++17
5 / 100
 57 ms 8008 KB 
#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(){
		if(history.empty()) return {1, (int) 3e9, (int) 3e9};
		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) 3e9, (int) 3e9};
	if(k == 1){
		cout << res1[1] << ' ' << res1[2] << ' ' << res1[0] << endl;
		return 0; 
	}
	for(int i = 0;i < n-1;i++){
		x2.rollback();
		x1.add(v[i]);
		while(i < n-1 and v[i].first == v[i+1].first){
			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]);
		while(i < n-1 and v[i].second == v[i+1].second){
			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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 57 ms 7856 KB Output is correct
8 Correct 56 ms 7860 KB Output is correct
9 Correct 52 ms 7976 KB Output is correct
10 Correct 57 ms 8008 KB Output is correct
11 Correct 55 ms 8004 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -