#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2e5 + 10;
const int INF = 2e9;
struct node{
int min, id;
node(){
min = INF;
}
};
int a[MAXN], b[MAXN], t[MAXN], s[MAXN];
node seg[4 * MAXN];
int bit[3 * MAXN];
int n, k;
vector<int> all_c;
int ind(int x){
return lower_bound(all_c.begin(), all_c.end(), x) - all_c.begin() + 1;
}
void update(int x, int lx, int rx, int i, int val){
if(rx < i || lx > i) return;
if(lx == rx){
seg[x].min = val;
seg[x].id = lx;
return;
}
int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;
update(lc, lx, m, i, val);
update(rc, m + 1, rx, i, val);
seg[x].min = min(seg[lc].min, seg[rc].min);
seg[x].id = (seg[lc].min < seg[rc].min ? seg[lc].id : seg[rc].id);
}
pair<int, int> query(int x, int lx, int rx, int l, int r){
if(rx < l || lx > r) return {INF, INF};
if(l <= lx && rx <= r) return {seg[x].min, seg[x].id};
int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;
return min(query(lc, lx, m, l, r), query(rc, m + 1, rx, l, r));
}
void bit_add(int pos, int x){
for(int i=pos; i<=(2 * n + k); i+=(i&-i)){
bit[i] += x;
}
}
int bit_query(int pos){
int sum = 0;
for(int i=pos; i>0; i-=(i&-i)){
sum += bit[i];
}
return sum;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
vector<pair<int, int>> ord;
for(int i=1; i<=n; i++){
cin >> a[i] >> b[i];
if(a[i] > b[i]){
s[i] = 1;
swap(a[i], b[i]);
}
all_c.push_back(a[i]);
all_c.push_back(b[i]);
ord.push_back({b[i], i});
}
sort(ord.begin(), ord.end());
for(int i=1; i<=k; i++){
cin >> t[i];
all_c.push_back(t[i]);
}
sort(all_c.begin(), all_c.end());
all_c.erase(unique(all_c.begin(), all_c.end()), all_c.end());
for(int i=0; i<n; i++) update(1, 1, n, i + 1, a[ord[i].second]);
ll ans = 0;
int tot = 0;
for(int i=k; i>=1; i--){
int pos = upper_bound(ord.begin(), ord.end(), make_pair(t[i], INF)) - ord.begin() + 1;
if(pos > (int) ord.size()){
bit_add(ind(t[i]), 1);
tot ++;
continue;
}
int j = query(1, 1, n, pos, n).second - 1;
while(j < n && a[ord[j].second] <= t[i]){
if((tot - bit_query(ind(a[ord[j].second]) - 1)) % 2 == 0){
ans += b[ord[j].second];
} else ans += a[ord[j].second];
a[ord[j].second] = INF;
update(1, 1, n, j + 1, INF);
j = query(1, 1, n, pos, n).second - 1;
}
bit_add(ind(t[i]), 1);
tot ++;
}
for(int i=0; i<n; i++){
if(a[ord[i].second] != INF){
if(s[ord[i].second]) swap(b[ord[i].second], a[ord[i].second]);
if((tot - bit_query(ind(a[ord[i].second]) - 1)) % 2 == 0){
ans += a[ord[i].second];
} else ans += b[ord[i].second];
}
}
cout << ans << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |