Submission #894747

#	Time	Username	Problem	Language	Result	Execution time	Memory
894747		beaboss	Hamburg Steak (JOI20_hamburg)	C++14	0 / 100	5 ms	1116 KiB

hamburg

// 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
• Subtask 2: 0 / 1
• Subtask 3: 0 / 3
• Subtask 4: 0 / 6
• Subtask 5: 0 / 1
• Subtask 6: 0 / 3
• Subtask 7: 0 / 6
• Subtask 8: 0 / 79