oj.uz

Submission #894747

# Submission time Handle Problem Language Result Execution time Memory
894747 2023-12-28T20:57:21 Z beaboss Hamburg Steak (JOI20_hamburg) C++14
0 / 100
 5 ms 1116 KB 
// Source: https://oj.uz/problem/view/JOI20_hamburg
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

map<int, set<pii> > mp;

vector<vi> loc;

pii find() {
	set<pii> prv = {{0, 0}};

	int best = -1;
	pii pos;

	for (auto row: mp) {
		set<pii> cur = {};
		int pref = 0;
		for (auto val: row.s) {
			pref += val.s;
			int here = (*prev(prv.upper_bound({val.f, -1}), 1)).s + pref;
			cur.insert({val.f, here});
			if (here > best) {
				best = here;
				pos={row.f, val.f};
			}
		}

		prv = cur;
		prv.insert({-1, 0});
	}

	return pos;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);


	int n, k;
	cin >> n >> k;

	FOR(i, 1, n + 1) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;

		loc.pb({a, b, c, d});

		mp[a].insert({b, 1});
		mp[a].insert({d + 1, -1});
		mp[c+1].insert({b, -1});
		mp[c+1].insert({d + 1, -1});
	}

	FOR(i, 0, k) {
		pii best = find();
		cout << best.f << ' ' << best.s << endl;
	}

}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 1.0

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

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -