#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+3;
int A[N], B[N], C[N];
int x1[N], x2[N], pa[N];
map<int, int> M; int m;
// persistent segment tree
struct node{
node *l, *r;
int tl, tr, cnt;
node(int L, int R, int cnt) : l(nullptr), r(nullptr), tl(L), tr(R), cnt(cnt){};
~node(){};
};
void build(node*& t, int l, int r){
t = new node(l, r, 0);
if(l == r) return;
int mid = (l + r) / 2;
build(t->l, l, mid);
build(t->r, mid + 1, r);
}
node* upd(node* t, int tl, int tr, int q, int delta){
if(tl == tr){
node* ret = new node(tl, tr, (t ? t->cnt : 0) + delta);
return ret;
}
int tm = (tl + tr) / 2;
node* ret = new node(tl, tr, t->cnt);
ret->l = t->l, ret->r = t->r;
if(q <= tm){
ret->l = upd(t->l, tl, tm, q, delta);
}else{
ret->r = upd(t->r, tm + 1, tr, q, delta);
}
ret->cnt = (ret->l ? ret->l->cnt : 0) + (ret->r ? ret->r->cnt : 0);
return ret;
}
int qry(node* t, int r){
if(t->tl == t->tr) return t->cnt;
if(r <= t->l->tr) return qry(t->l, r);
else return t->l->cnt + qry(t->r, r);
}
int qry(node* t, int l, int r){
return qry(t, r) - qry(t, l - 1);
}
node* T[N];
// MT merge sort tree
namespace MTree{
vector<int> t[N * 4];
vector<int> a, b;
void build(int v, int l, int r){
if(l == r){
t[v].push_back(C[l]);
return;
}
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m + 1, r);
merge(t[v * 2 + 1].begin(), t[v * 2 + 1].end(), t[v * 2 + 2].begin(), t[v * 2 + 2].end(), back_inserter(t[v]));
}
int last(int v, int l, int r, int vl, int vr){
if(l == r) return max(0, l - 1);
if(lower_bound(t[v * 2 + 2].begin(), t[v * 2 + 2].end(), vl) != upper_bound(t[v * 2 + 2].begin(), t[v * 2 + 2].end(), vr)){
return last(v * 2 + 2, (l + r) / 2 + 1, r, vl, vr);
}else{
return last(v * 2 + 1, l, (l + r) / 2, vl, vr);
}
}
};
int32_t main(){
int n, k;
cin >> n >> k;
for(int i = 0; i < n; i++){
cin >> A[i] >> B[i];
x1[i] = min(A[i], B[i]);
x2[i] = max(A[i], B[i]);
pa[i] = x1[i] != A[i];
}
for(int i = 1; i <= k; i++){
cin >> C[i];
}
{
vector<int> v; for(int i = 1; i <= k; i++) v.push_back(C[i]);
sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin());
int idx = 0; for(auto i : v) M[i] = ++idx; M[1 << 30] = ++idx; m = idx;
for(int i = 1; i <= k; i++) C[i] = M[C[i]];
}
MTree::build(0, 0, k - 1);
build(T[0], 0, m);
for(int i = 1; i <= k; i++){
T[i] = upd(T[i - 1], 0, m, C[i], 1);
}
long long ans = 0;
for(int i = 0; i < n; i++){
int y1 = M.lower_bound(x1[i])->second;
int y2 = M.lower_bound(x2[i])->second;
int l = MTree::last(0, 0, k - 1, y1, y2 - 1);
if(l != 0) pa[i] = true;
int cnt = qry(T[k], y2, m) - qry(T[l], y2, m);
pa[i] ^= cnt % 2;
ans += pa[i] ? x2[i] : x1[i];
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
