#include <bits/stdc++.h>
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 2e5 + 128;
int n, k;
int a[N], b[N], c[N];
vector <int> t[4 * N];
void build(int v, int tl, int tr) {
if (tl == tr) {
t[v].push_back(c[tl]);
return;
}
int tm = (tl + tr) >> 1;
build(v << 1, tl, tm);
build(v << 1 | 1, tm + 1, tr);
merge(all(t[v << 1]), all(t[v << 1 | 1]), back_inserter(t[v]));
}
int get(int l, int r, int x, int v, int tl, int tr) {
if (tl > r || tr < l)
return 0;
if (l <= tl && tr <= r)
return (int)t[v].size() - (int)(lower_bound(all(t[v]), x) - t[v].begin());
int tm = (tl + tr) >> 1;
return get(l, r, x, v << 1, tl, tm) +
get(l, r, x, v << 1 | 1, tm + 1, tr);
}
const int INF = 2e9 + 128;
int mx[4 * N];
void update(int pos, int val, int v, int tl, int tr) {
if (tl > pos || tr < pos)
return;
if (tl == tr) {
mx[v] = val;
return;
}
int tm = (tl + tr) >> 1;
update(pos, val, v << 1, tl, tm);
update(pos, val, v << 1 | 1, tm + 1, tr);
mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
}
int rightmost(int l, int r, int x, int v, int tl, int tr) {
if (tl > r || tr < l || mx[v] < x)
return -1;
if (tl == tr)
return tl;
int tm = (tl + tr) >> 1;
if (l <= tl && tr <= r) {
if (mx[v << 1 | 1] >= x)
return rightmost(l, r, x, v << 1 | 1, tm + 1, tr);
else if (mx[v << 1] >= x)
return rightmost(l, r, x, v << 1, tl, tm);
return -1;
}
return max(rightmost(l, r, x, v << 1, tl, tm), rightmost(l, r, x, v << 1 | 1, tm + 1, tr));
}
void solve() {
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> a[i] >> b[i];
for (int i = 0; i < k; i++)
cin >> c[i];
build(1, 0, k - 1);
vector <int> order(n);
iota(all(order), 0);
sort(all(order), [&](const int& x, const int& y) -> bool {
return max(a[x], b[x]) < max(a[y], b[y]);
});
vector < pair<int, int> > to_add;
for (int i = 0; i < k; i++)
to_add.push_back(make_pair(c[i], i));
sort(all(to_add));
ll ans = 0;
vector <int> pref(k);
for (int i = 0; i < k; i++)
pref[i] = max((i ? pref[i - 1] : 0), c[i]);
for (int i = 0; i < k; i++)
update(i, -INF, 1, 0, k - 1);
int pt = 0;
for (auto& i : order) {
int x = -1;
if (a[i] > b[i]) {
x = (int)(lower_bound(all(pref), a[i]) - pref.begin());
if (x == k) {
ans += a[i];
continue;
}
swap(a[i], b[i]);
}
assert(a[i] <= b[i]);
while (pt < k && to_add[pt].first < b[i])
update(to_add[pt].second, to_add[pt].first, 1, 0, k - 1), pt++;
int pos = rightmost(x + 1, k - 1, a[i], 1, 0, k - 1);
if (pos < 0) {
ans += a[i];
continue;
}
int lefts = get(pos + 1, k - 1, b[i], 1, 0, k - 1);
ans += ((lefts % 2 == 0) ? b[i] : a[i]);
}
cout << ans << '\n';
}
main() {
boost;
solve();
return 0;
}
Compilation message
fortune_telling2.cpp:130:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
130 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
21084 KB |
Output is correct |
| 2 |
Correct |
8 ms |
21084 KB |
Output is correct |
| 3 |
Correct |
7 ms |
21084 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
21084 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
21084 KB |
Output is correct |
| 2 |
Correct |
8 ms |
21084 KB |
Output is correct |
| 3 |
Correct |
7 ms |
21084 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
21084 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
21084 KB |
Output is correct |
| 2 |
Correct |
8 ms |
21084 KB |
Output is correct |
| 3 |
Correct |
7 ms |
21084 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
21084 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
