#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 upd(int p){
for(++p;p<N;p+=p&-p) ft[p]++;
}
int query(int p){
int s=0;
for(;p>0;p-=p&-p) s+=ft[p];
return s;
}
int query(int l, int r){
return query(r)-query(l);
}
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 suff_min(k+1),suff_max(k+1);
suff_min[k]=INF,suff_max[k]=-INF;
dforn(i,k){
suff_min[i]=min(suff_min[i+1],t[i]);
suff_max[i]=max(suff_max[i+1],t[i]);
}
vector<tuple<int,int,int>> queries;
forn(i,n){
auto[c,d]=minmax(a[i],b[i]);
int lo=-1,hi=k;
while(hi-lo>1){
int mid=(lo+hi)/2;
if(suff_min[mid]>=d||suff_max[mid]<c) hi=mid;
else lo=mid;
}
queries.eb(d,hi,i);
}
vi order(k); iota(all(order),0);
sort(all(order),[&](const int &lhs, const int &rhs){
return t[lhs]>t[rhs];
});
sort(all(queries));
reverse(all(queries));
ll ret=0;
int j=0;
for(auto[d,p,i]:queries){
while(j<k&&t[order[j]]>=d) upd(order[j++]);
bool f=query(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... |