#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+3;
int A[N], B[N], C[N];
int x1[N], x2[N], pa[N];
map<int, int> M; int m;
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 ? 0 : t->cnt) + 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);
cout << ret->tl << ' ' << ret->tr << ' ' << ret->cnt << endl;
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];
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]];
}
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 = 0, r = k, tot = qry(T[k], y1, y2 - 1);
while(l != r){
int mid = (l + r) / 2;
if(qry(T[mid], y1, y2 - 1) == tot){
r = mid;
}else{
l = mid + 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 |
16 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
