#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define int long long
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5+10 + 10, inf = 1e9+10 , mod = 1e9 + 7 ;
int a[maxn] , b[maxn] , u[maxn] ;
vector <int> cm ;
vector <int> ch[maxn] ;
struct node{
int mx , sm ;
node(){
mx = -inf ;sm = 0;
}
};
node seg[12*maxn] ;
void bui(){
int n = sz(cm) ;
rep(i , 1 , 4*n){
seg[i].mx = -inf ;
seg[i].sm = 0 ;
}
}
node operator+(node a, node b){
node r ;
r.sm = a.sm + b.sm ;
r.mx = max(a.mx , b.mx) ;
return r ;
}
void upd(int x , pii a , int p = 1, int l = 0, int r = sz(cm)-1){
int mid = (l+r)/2 ,pl =p<<1,pr=p<<1|1;
if(l > x || r < x)return ;
if(l == r){
seg[p].mx = max(seg[p].mx , a.F) ;
seg[p].sm++;
return ;
}
upd(x,a,pl,l,mid);
upd(x,a,pr,mid+1,r);
seg[p] = seg[pl] + seg[pr] ;
}
node que(int le ,int ri ,int p = 1 , int l = 0, int r =sz(cm)-1){
int mid = (l+r)/2 ,pl =p<<1,pr=p<<1|1;
if(le <= l && r <= ri)return seg[p] ;
if(ri <= mid){
return que(le,ri,pl,l,mid);
}
if(le > mid){
return que(le,ri,pr,mid+1,r);
}
return que(le,ri,pl,l,mid) + que(le,ri,pr,mid+1,r) ;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n , k ;
cin >> n >> k ;
rep(i ,1 ,n){
cin >> a[i] >> b[i] ;
cm.pb(a[i]) ;cm.pb(b[i]) ;
}
rep(i ,1 ,k){
cin >> u[i] ;
cm.pb(u[i]);
}
sort(all(cm));
cm.resize(unique(all(cm))-cm.begin()) ;
rep(i ,1 , n){
a[i] = lower_bound(all(cm) , a[i]) - cm.begin() ;
b[i] = lower_bound(all(cm) , b[i]) - cm.begin() ;
u[i] = lower_bound(all(cm) , u[i]) - cm.begin() ;
}
rep(i ,1 ,k){
upd(u[i] , {i,0});
}
rep(i , 1, n){
if(a[i] == b[i]){
continue ;
}
int x = que(min(a[i] , b[i]) , max(a[i] , b[i])-1).mx ;
if(x==-inf){
x =0;
}else{
if(a[i] < b[i])swap(a[i] , b[i]) ;
}
ch[x+1].pb(i) ;
}
bui();
per(i , k+1 , 1){
if(i!=k+1){
upd(u[i] , {0 , 1});
}
for(int x : ch[i]){
if(que(max(b[x],a[x]) , sz(cm)-1).sm %2==1){
swap(a[x] , b[x]) ;
}
}
}
int ans =0;
rep(i , 1,n){
ans += cm[a[i]] ;
}
cout << ans << '\n';
return 0 ;
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
45656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
45656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
45656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
