#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define fi first
#define se second
int n,m,q;
int ft[200005];
void upd(int p, int v){
for(;p<=m;p+=(p & -p))ft[p] += v;
}
int query(int p){
int sum = 0;
for(;p;p-=(p & -p))sum += ft[p];
return sum;
}
pi A[200005];
bool cmp(pi a, pi b){
return max(a.fi, a.se) < max(b.fi, b.se);
}
pi Q[200005];
struct node{
int s,e,m,val;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e)/2;
val = 0;
if(s != e)l = new node(s, m), r = new node(m+1, e), val = max(l->val, r->val);
else val = Q[s].se;
}
int query(int a, int b){
if(a == s && b == e)return val;
else if(b <= m)return l->query(a, b);
else if(a > m)return r->query(a, b);
else return max(l->query(a, m), r->query(m+1, b));
}
}*root;
void solve(){
cin >> n >> m;
for(int i=1;i<=n;i++)cin >> A[i].fi >> A[i].se;
sort(A+1, A+n+1, cmp);
for(int i=1;i<=m;i++)cin >> Q[i].fi, Q[i].se = i;
sort(Q+1, Q+m+1);
root = new node(1, m);
int in = 1, cur = 0;
Q[0].fi = -1e9;
int ans = 0;
for(int i=1;i<=n;i++){
while(in <= m && Q[in].fi < max(A[i].fi, A[i].se))cur = max(cur, Q[in].se), in++;
int tmp;
if(Q[in-1].fi < min(A[i].fi, A[i].se)){
tmp = m - in + 1;
ans += (tmp%2 ? A[i].se : A[i].fi);
}
else {
int lo = 1, hi = in, ans2 = in + 1;
while(lo <= hi){
int mid = (lo + hi)>>1;
if(Q[mid].fi >= min(A[i].fi, A[i].se))ans2 = mid, hi = mid - 1;
else lo = mid + 1;
}
tmp = m - root->query(ans2, in - 1);
//cout << tmp << '\n';
ans += (tmp%2 ? min(A[i].fi, A[i].se) : max(A[i].fi, A[i].se));
}
//cout << ans << ' ' << A[i].fi << ' ' << A[i].se << '\n';
}
cout << ans;
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
Compilation message
fortune_telling2.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
75 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
