#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
struct MNode { int a = -1;
MNode() {}
MNode(int x) : a(x) {}
friend MNode operator+(const MNode &a, const MNode &b) {
return MNode(max(a.a, b.a));
}
};
struct PNode { int a = 0;
PNode() {}
PNode(int x) : a(x) {}
friend PNode operator+(const PNode &a, const PNode &b) {
return PNode(a.a^b.a);
}
};
template<class Node>
struct SegTree {
int n;
vector<Node> tree;
SegTree(int N) : n(N), tree(2*n) {}
void upd(int pos, Node val) {
for(tree[pos+=n]=val;pos/=2;)
tree[pos] = tree[2*pos]+tree[2*pos+1];
}
Node query(int l, int r) {
Node res;
for(l += n, r += n; l < r; l>>=1,r>>=1) {
if(l&1) res = res + tree[l++];
if(r&1) res = tree[--r] + res;
}
return res;
}
};
int n, k;
vector<array<int, 2>> f, ops_sorted;
vector<int> ops, start;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
f.resize(n);
start.resize(n);
for(auto &[a, b] : f) cin >> a >> b;
ops.resize(k);
for(auto &i : ops) cin >> i;
for(int i = 0; i < k; i++) ops_sorted.push_back({ops[i], i});
for(int i = 0; i < n; i++) ops_sorted.push_back({max(f[i][0], f[i][1])-1, i|(1<<30)});
sort(all(ops_sorted));
SegTree<MNode> ms(n);
for(auto [v, i] : ops_sorted) {
if(i&(1<<30)) {
i -= 1<<30;
int pos = n;
for(int z = 1<<18; z>>=1;)
if(pos-z>=0 && ms.query(pos-z, n).a < min(f[i][0], f[i][1]))
pos -= z;
start[i] = pos;
} else {
ms.upd(i, MNode(v));
}
}
SegTree<PNode> xr(n);
ops_sorted.clear();
for(int i = 0; i < k; i++) ops_sorted.push_back({ops[i], i});
for(int i = 0; i < n; i++) ops_sorted.push_back({max(f[i][0], f[i][1]), i-(1<<30)});
sort(all(ops_sorted), greater<>());
ll sum = 0;
for(auto [v, i] : ops_sorted) {
if(i<0) {
i+=1<<30;
if(start[i] && f[i][0] < f[i][1]) swap(f[i][0], f[i][1]);
if(xr.query(start[i], n).a)
swap(f[i][0], f[i][1]);
sum += f[i][0];
} else {
xr.upd(i, PNode(1));
}
}
cout << sum << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
