#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second
const int MAXN = 2e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
struct Node {
int mi = INF, mx = -INF;
int qtdmx = 0;
};
Node merge(const Node& a, const Node& b) {
Node ans;
ans.mi = min(a.mi, b.mi);
ans.mx = max(a.mx, b.mx);
if (ans.mx == a.mx) ans.qtdmx += a.qtdmx;
if (ans.mx == b.mx) ans.qtdmx += b.qtdmx;
return ans;
}
Node seg[4*MAXN];
int v[MAXN];
void build(int node, int l, int r) {
if (l == r) {
seg[node].mi = seg[node].mx = v[l];
seg[node].qtdmx = 1;
return;
}
int m = (l+r)/2;
build(2*node, l, m);
build(2*node + 1, m + 1, r);
seg[node] = merge(seg[2*node], seg[2*node + 1]);
}
// find last value that is smaller than x
int bsearch(int node, int l, int r, int x) {
if (l == r) {
return l;
}
int m = (l+r)/2;
if (seg[2*node + 1].mi < x) return bsearch(2*node + 1, m + 1, r, x);
else if (seg[2*node].mi < x) return bsearch(2*node, l, m, x);
else return 0;
}
void update(int node, int l, int r, int po) {
if (l == r) {
seg[node].mi = seg[node].mx = INF;
return;
}
int m = (l+r)/2;
if (po <= m) update(2*node, l, m, po);
else update(2*node + 1, m + 1, r, po);
seg[node] = merge(seg[2*node], seg[2*node + 1]);
}
Node empt;
Node query(int node, int l, int r, int tl, int tr) {
if ((tr < l) || (r < tl)) return empt;
if ((tl <= l) && (r <= tr)) return seg[node];
int m = (l+r)/2;
return merge(query(2*node, l, m, tl, tr), query(2*node + 1, m + 1, r, tl, tr));
}
bool comp(pii a, pii b) {
return (min(a.fr, a.se) < min(b.fr, b.se));
}
int32_t main() {
int n, k;
cin >> n >> k;
vector<pii> c(n);
for (int i = 0; i < n; i++) {
cin >> c[i].fr >> c[i].se;
}
vector<pii> po;
for (int i = 1; i <= k; i++) {
cin >> v[i];
po.push_back({v[i], i});
}
sort(po.begin(), po.end(), greater<pii>());
sort(c.begin(), c.end(), comp);
build(1, 1, k);
int ans = 0;
for (auto u : c) {
if (u.fr == u.se) {
ans += u.fr;
//cout << u.fr << " " << u.se << " " << u.fr << "\n";
continue;
}
while ((!po.empty()) && (po.back().fr < min(u.fr, u.se))) {
//cout << "rem " << po.back().fr << "\n";
update(1, 1, k, po.back().se);
po.pop_back();
}
if (po.empty()) {
ans += u.fr;
//cout << u.fr << " " << u.se << " " << u.fr << "\n";
continue;
}
if (u.fr < u.se) {
int p = bsearch(1, 1, k, u.se);
if (p == k) {
ans += u.se;
//cout << u.fr << " " << u.se << " " << u.se << "\n";
continue;
}
int comeco = 0;
int qtd = (k - p);
Node q = query(1, 1, n, p + 1, k);
if (q.mx == INF) qtd -= q.qtdmx;
if (p == 0) {
comeco = 1;
}
qtd += comeco;
if ((qtd % 2LL) == 1LL) {
ans += u.fr;
//cout << u.fr << " " << u.se << " " << u.fr << "\n";
}
else {
ans += u.se;
//cout << u.fr << " " << u.se << " " << u.se << "\n";
}
continue;
} else {
swap(u.fr, u.se);
int p = bsearch(1, 1, k, u.se);
if (p == k) {
ans += u.se;
cout << u.fr << " " << u.se << " " << u.se << "\n";
continue;
}
int comeco = 0;
int qtd = (k - p);
Node q = query(1, 1, n, p + 1, k);
if (q.mx == INF) qtd -= q.qtdmx;
if (p == 0) {
comeco = 1;
}
qtd += comeco;
if ((qtd % 2LL) == 1LL) {
ans += u.fr;
//cout << u.fr << " " << u.se << " " << u.fr << "\n";
}
else {
ans += u.se;
//cout << u.fr << " " << u.se << " " << u.se << "\n";
}
continue;
}
}
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
