Submission #901689

#	Time	Username	Problem	Language	Result	Execution time	Memory
901689		MilosMilutinovic	Hotel (CEOI11_hot)	C++14	100 / 100	1270 ms	197544 KiB

hot

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXT = 4050000;

struct seg {
	int lim;
	pair<int, int> tree[MAXT];
	void init(int n) {
		for (lim = 1; lim <= n; lim <<= 1);
	}
	void update(int p, int v) {
		p += lim; tree[p] = {v, p - lim};
		for (p >>= 1; p; p >>= 1) tree[p] = max(tree[p * 2], tree[p * 2 + 1]);
	}
	pair<int, int> query(int l, int r) {
		pair<int, int> res = {0, 0};
		for (l += lim, r += lim + 1; l < r; l >>= 1, r >>= 1) {
			if (l & 1) res = max(res, tree[l++]);
			if (r & 1) res = max(res, tree[--r]);
		}
		return res;
	}
} seg;

struct compress {
	vector<int> xs;
	void add(int x) {
		xs.push_back(x);
	}
	void build() {
		sort(all(xs));
		xs.erase(unique(all(xs)), xs.end());
	}
	int val(int x) {
		return (int)(lower_bound(all(xs), x) - xs.begin()); 
	}
} comp;

int n, m, o;
vector<int> vals[MAXT];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> o;
	vector<pi> c(n);
	for (int i = 0; i < n; i++) {
		cin >> c[i][0] >> c[i][1];
		comp.add(c[i][1]);
	}
	vector<pi> d(m);
	for (int i = 0; i < m; i++) {
		cin >> d[i][0] >> d[i][1];
		comp.add(d[i][1]);
	}
	comp.build();
	for (int i = 0; i < n; i++) 
		c[i][1] = comp.val(c[i][1]);
	for (int i = 0; i < m; i++)
		d[i][1] = comp.val(d[i][1]);
	sort(all(c));
	sort(all(d));
	for (int i = 0; i < m; i++) 
		vals[d[i][1]].push_back(d[i][0]);
	seg.init(sz(comp.xs));
	for (int i = 0; i < MAXT; i++) {
		if (sz(vals[i]) == 0) continue;
		sort(all(vals[i]));
		seg.update(i, vals[i].back());
		vals[i].pop_back();
	}
	set<int> free;
	for (int i = 0; i < n; i++) {
		free.insert(i);
	}
	set<tuple<int, int, int>> st;
	for (int i = 0; i < n; i++) {
		pair<int, int> f = seg.query(i == 0 ? 0 : c[i - 1][1] + 1, c[i][1]);
		if (f.first != 0)
			st.emplace(f.first - c[i][0], f.second, i);
	}
	lint res = 0;
	while (o-- && sz(st) > 0) {
		if (get<0>(*prev(st.end())) <= 0) break;
		res += get<0>(*prev(st.end()));
		int x = get<1>(*prev(st.end()));
		int y = get<2>(*prev(st.end()));
		st.erase(prev(st.end()));
		if (vals[x].empty()) {
			seg.update(x, 0);
		} else {
			seg.update(x, vals[x].back());
			vals[x].pop_back();
		}
		free.erase(y);
		auto it = free.lower_bound(y);
		if (it != free.end()) {
			int i = *it;
			pair<int, int> f = seg.query(c[y][1] + 1, c[i][1]);
			if (f.first != 0) 
				st.erase(st.find({f.first - c[i][0], f.second, i}));
			int lft = (it == free.begin() ? 0 : c[*prev(it)][1] + 1);
			f = seg.query(lft, c[i][1]);
			if (f.first != 0)
				st.emplace(f.first - c[i][0], f.second, i);
		}
	}
	cout << res << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10