oj.uz

Submission #787547

# Submission time Handle Problem Language Result Execution time Memory
787547 2023-07-19T09:29:46 Z 박영우(#10035) Hamburg Steak (JOI20_hamburg) C++17
6 / 100
 1098 ms 45996 KB 
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1001010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int L[MAX];
int R[MAX];
int U[MAX];
int D[MAX];
multiset<int> ls;
multiset<int> rs;
multiset<int> us;
multiset<int> ds;
void add(int x) {
	ls.insert(L[x]);
	rs.insert(R[x]);
	us.insert(U[x]);
	ds.insert(D[x]);
}
void remove(int x) {
	ls.erase(ls.find(L[x]));
	rs.erase(rs.find(R[x]));
	us.erase(us.find(U[x]));
	ds.erase(ds.find(D[x]));
}
bool chk() {
	if (ls.empty()) return true;
	return *ls.rbegin() <= *rs.begin() && *ds.rbegin() <= *us.begin();
}
void print() {
	cout << *ls.rbegin() << bb << *ds.rbegin() << ln;
}
void swap2(int i, int j) {
	swap(L[i], L[j]);
	swap(R[i], R[j]);
	swap(U[i], U[j]);
	swap(D[i], D[j]);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, K;
	cin >> N >> K;
	if (K == 1) {
		int i;
		int xl, yl;
		xl = yl = 0;
		int a, b, c, d;
		for (i = 1; i <= N; i++) {
			cin >> a >> b >> c >> d;
			xl = max(xl, a);
			yl = max(yl, b);
		}
		cout << xl << bb << yl;
	}
	if (K > 1) {
		int i;
		for (i = 1; i <= N; i++) cin >> L[i] >> D[i] >> R[i] >> U[i];
	}
	if (K == 2) {
		int i;
		for (i = 1; i <= N; i++) if (U[i] < U[1]) swap2(1, i);
		for (i = 2; i <= N; i++) add(i);
		vector<pii> st;
		for (i = 2; i <= N; i++) if (D[i] <= U[1] && U[1] <= U[i]) st.emplace_back(L[i], i), st.emplace_back(R[i], -i);
		st.emplace_back(L[1], 0);
		sort(st.begin(), st.end());
		for (auto& [a, b] : st) {
			if (!b) {
				if (chk()) {
					cout << a << bb << U[1] << ln;
					print();
					return 0;
				}
				continue;
			}
			if (b > 0) {
				remove(b);
				if (L[1] <= a && a <= R[1]) {
					if (chk()) {
						cout << a << bb << U[1] << ln;
						print();
						return 0;
					}
				}
			}
			else add(-b);
		}
	}
}

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
0 / 3.0

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

Subtask #4
0 / 6.0

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

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 62 ms 988 KB Output is correct
6 Correct 61 ms 1064 KB Output is correct
7 Correct 67 ms 1064 KB Output is correct
8 Correct 62 ms 1072 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 3 ms 848 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 872 ms 45804 KB Output is correct
6 Correct 1098 ms 45996 KB Output is correct
7 Correct 954 ms 43948 KB Output is correct
8 Correct 867 ms 43984 KB Output is correct

Subtask #7
0 / 6.0

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

Subtask #8
0 / 79.0

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