// Code by Parsa Eslami
#include <bits/stdc++.h>
#define pii pair<int,int>
#define bit(i,j) ((j>>i)&1)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
using namespace std;
const int N=2e5+4;
const int lg=20;
pii a[N];
pii b[N];
int mx[lg][N],n,k;
int pw[lg];
long long ans;
struct fenwick{
int fen[N];
void add(int k){
while(k<N){
fen[k]++;
k+=(k&(-k));
}
}
int get(int k){
int rt=0;
while(k>0){
rt+=fen[k];
k-=(k&(-k));
}
return rt;
}
};fenwick fen;
bool cmp(pii a,pii b){
return (max(a.F,a.S)<max(b.F,b.S));
}
int MX(int l,int r){
int LG=31-__builtin_clz(r-l+1);
return max(mx[LG][l],mx[LG][r-pw[LG]+1]);
}
int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(0);
pw[0]=1; FOR(i,1,lg-1) pw[i]=pw[i-1]*2;
cin>>n>>k;
FOR(i,1,n) cin>>a[i].F>>a[i].S;
sort(a+1,a+1+n,cmp);
FOR(i,1,k){ cin>>b[i].F; b[i].S=i;}
sort(b+1,b+1+k);
FOR(i,1,k) mx[0][i]=b[i].S;
FOR(j,1,lg-1) FOR(i,1,k-pw[j]+1){
mx[j][i]=max(mx[j-1][i],mx[j-1][i+pw[j-1]]);
}
int p=k;
FORR(i,n,1){
if(a[i].F==a[i].S){
ans+=a[i].F;
continue;
}
int mx=max(a[i].F,a[i].S);
int mn=a[i].F+a[i].S-mx;
while(p>0&&b[p].F>=mx){
fen.add(b[p].S);
p--;
}
int l=0,r=k+1;
int R,L;
while(r-l>1){
int mid=(r+l)/2;
if(b[mid].F<mx) l=mid;
else r=mid;
}
R=l;
l=0,r=k+1;
while(r-l>1){
int mid=(r+l)/2;
if(b[mid].F>=mn) r=mid;
else l=mid;
}
L=r;
int x;
if(L>R) x=-1;
else x=MX(L,R);
if(x==-1){
if(fen.get(n)&1) ans+=a[i].S;
else ans+=a[i].F;
}else{
if((fen.get(n)-fen.get(x))&1) ans+=mn;
else ans+=mx;
}
}
cout<<ans<<'\n';
return 0;
}
| # |
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 |
- |
