#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";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
127068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
127108 KB |
Output is correct |
| 2 |
Correct |
32 ms |
127064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
127068 KB |
Output is correct |
| 2 |
Correct |
31 ms |
127064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
127064 KB |
Output is correct |
| 2 |
Correct |
31 ms |
127060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
128148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
131172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
134348 KB |
Output is correct |
| 2 |
Correct |
91 ms |
134612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
359 ms |
147656 KB |
Output is correct |
| 2 |
Correct |
149 ms |
139568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
558 ms |
167916 KB |
Output is correct |
| 2 |
Correct |
654 ms |
196164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
631 ms |
178116 KB |
Output is correct |
| 2 |
Correct |
977 ms |
197544 KB |
Output is correct |
| 3 |
Correct |
1270 ms |
185800 KB |
Output is correct |
