oj.uz

답안 #901683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
901683 2024-01-09T23:55:10 Z MilosMilutinovic Hotel (CEOI11_hot) C++14
0 / 100
 2799 ms 262144 KB 
#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};
		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(0, 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(y + 1, i);
			if (f.first != 0) 
				st.erase(st.find({f.first - c[i][0], f.second, i}));
			int lft = (it == free.begin() ? 0 : *prev(it) + 1);
			f = seg.query(lft, i);
			if (f.first != 0)
				st.emplace(f.first - c[i][0], f.second, i);
		}
	}
	cout << res << "\n";
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 138 ms 257668 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 129 ms 257620 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 139 ms 257660 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 131 ms 257616 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 136 ms 260532 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2454 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2536 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2515 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2759 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2799 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -