#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 2e5 + 5, inf = 1e9;
int n, k;
int s[4 * N], sum[4 * N], lst[N];
bool flip[N];
void upd(int i, int x, int id = 1, int l = 1, int r = k) {
if (l == r) {
s[id] = x;
sum[id] = x != inf;
return;
}
int md = (l + r) / 2;
if (i <= md) {
upd(i, x, id * 2, l, md);
} else {
upd(i, x, id * 2 + 1, md + 1, r);
}
s[id] = min(s[id * 2], s[id * 2 + 1]);
sum[id] = sum[id * 2] + sum[id * 2 + 1];
}
int qry(int u, int v, int id = 1, int l = 1, int r = k) {
if (u <= l && r <= v) {
return sum[id];
}
int md = (l + r) / 2;
if (v <= md) {
return qry(u, v, id * 2, l, md);
}
if (md < u) {
return qry(u, v, id * 2 + 1, md + 1, r);
}
return qry(u, v, id * 2, l, md) + qry(u, v, id * 2 + 1, md + 1, r);
}
int walk(int x, int id = 1, int l = 1, int r = k) {
if (l == r) {
return l;
}
int md = (l + r) / 2;
if (s[id * 2 + 1] <= x) {
return walk(x, id * 2 + 1, md + 1, r);
}
return walk(x, id * 2, l, md);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k;
vector<array<int, 3>> pt;
for (int i = 1; i <= n; ++i) {
int a, b; cin >> a >> b;
if (a < b) {
swap(a, b);
flip[i] = 1;
}
pt.push_back({a, b, i});
}
vector<array<int, 2>> ope;
for (int i = 0; i < k; ++i) {
int x; cin >> x;
ope.push_back({x, i + 1});
}
sort(ope.rbegin(), ope.rend());
sort(pt.begin(), pt.end(), [&](auto a, auto b) {
return a[1] > b[1];
});
fill(lst + 1, lst + n + 1, 1);
auto reset = [&]() {
for (int i = 1; i <= k; ++i) {
upd(i, inf);
}
};
reset();
int j = 0;
for (auto [a, b, id] : pt) {
while (j < k && ope[j][0] >= b) {
upd(ope[j][1], ope[j][0]);
++j;
}
if (s[1] > a) {
lst[id] = walk(a) + 1;
}
}
for (int i = 1; i <= k; ++i) {
upd(i, 0);
}
sort(pt.rbegin(), pt.rend());
j = 0;
long long res = 0;
reset();
for (auto [a, b, id] : pt) {
while (j < k && ope[j][0] >= a) {
upd(ope[j][1], ope[j][0]);
++j;
}
if (lst[id] > k) {
res += a;
} else {
int iter = qry(lst[id] + 1, k) % 2;
array<int, 2> s = {a, b};
if (flip[id]) {
swap(s[0], s[1]);
}
if (lst[id] != 1 && s[0] == b) {
swap(s[0], s[1]);
}
res += s[iter];
}
}
cout << res;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
