#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;
const int INF=1e9+20;
const int N=2e5+9;
int ft[N];
void add(int p){
for(++p;p<N;p+=p&-p) ft[p]++;
}
int get(int p){
int s=0;
for(;p>0;p-=p&-p) s+=ft[p];
return s;
}
int get(int l, int r){
return get(r)-get(l);
}
const int SZ=1<<18;
int st[2*SZ];
void upd(int p, int v){
st[p+=SZ]=v;
while(p/=2) st[p]=min(st[2*p],st[2*p+1]);
}
int find(int d){
if(st[1]>=d) return -1;
int u=1;
while(u<SZ){
u=2*u+1;
if(st[u]>=d) u--;
}
return u-SZ;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,k;
cin>>n>>k;
vi a(n),b(n);
forn(i,n) cin>>a[i]>>b[i];
vi t(k);
forn(i,k) cin>>t[i];
vi order(k); iota(all(order),0);
sort(all(order),[&](const int &lhs, const int &rhs){
return t[lhs]>t[rhs];
});
vector<ii> ask(n);
forn(i,n){
auto[c,d]=minmax(a[i],b[i]);
ask[i]={c,i};
}
sort(all(ask));
reverse(all(ask));
forn(i,2*SZ) st[i]=INF;
vector<tuple<int,int,int>> queries;
int j=0;
for(auto[c,i]:ask){
int d=a[i]+b[i]-c;
while(j<k&&t[order[j]]>=c){
upd(order[j],t[order[j]]);
j++;
}
int p=find(d);
queries.eb(d,p+1,i);
}
sort(all(queries));
reverse(all(queries));
ll ret=0;
j=0;
for(auto[d,p,i]:queries){
while(j<k&&t[order[j]]>=d) add(order[j++]);
bool f=get(p,k)%2;
if(p==0){
if(f) ret+=b[i];
else ret+=a[i];
}else{
if(f) ret+=min(a[i],b[i]);
else ret+=max(a[i],b[i]);
}
}
cout<<ret<<'\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... |