#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n"
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 2e5 + 5;
int n,k;
array<int,2> ar[N];
struct SegT{
vector<int> seg;
SegT(int n){seg.assign(4*n+5,0);}
void update(int rt,int l,int r,int ind,int u){
if(r<ind || l>ind) return;
if(l==r){
seg[rt]=max(seg[rt],u);
return;
}
int m=(l+r)/2;
update(rt*2,l,m,ind,u);update(rt*2+1,m+1,r,ind,u);
seg[rt]=max(seg[rt*2],seg[rt*2+1]);
}
int query(int rt,int l,int r,int gl,int gr){
if(r<gl || l>gr) return 0;
if(l>=gl && r<=gr) return seg[rt];
int m=(l+r)/2;
return max(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
}
};
vector<int> seg[4*N];
int xd[N];
void build(int rt,int l,int r){
if(l==r){
seg[rt].pb(xd[l]);
return;
}
int m=(l+r)/2;
build(rt*2,l,m);build(rt*2+1,m+1,r);
int p1=0,p2=0;
while(p1<sz(seg[rt*2]) && p2<sz(seg[rt*2+1])){
if(seg[rt*2][p1] <= seg[rt*2+1][p2]) seg[rt].pb(seg[rt*2][p1++]);
else seg[rt].pb(seg[rt*2+1][p2++]);
}
while(p1<sz(seg[rt*2])) seg[rt].pb(seg[rt*2][p1++]);
while(p2<sz(seg[rt*2+1])) seg[rt].pb(seg[rt*2+1][p2++]);
}
int query(int rt,int l,int r,int gl,int gr,int x){
if(r<gl || l>gr || gl>gr || l>r) return 0;
if(l>=gl && r<=gr){
int lol=lower_bound(all(seg[rt]),x)-seg[rt].begin();
return sz(seg[rt])-lol;
}
int m=(l+r)/2;
return query(rt*2,l,m,gl,gr,x) + query(rt*2+1,m+1,r,gl,gr,x);
}
void solve(){
cin >> n >> k;
map<int,int> mp;
for(int i=1;i<=n;i++){
int a,b;
cin >> a >> b;
ar[i]={a,b};
mp[a]=mp[b]=mp[a-1]=mp[b-1]=1;
}
for(int i=1;i<=k;i++){
cin >> xd[i];
mp[xd[i]]=1;
}
int p=0;
for(auto x:mp) mp[x.first]=++p;
SegT Seg(p);
for(int i=1;i<=k;i++) Seg.update(1,1,p,mp[xd[i]],i);
build(1,1,k);
int ans=0;
for(int i=1;i<=n;i++){
if(ar[i][0]==ar[i][1]){
ans+=ar[i][0];
continue;
}
int ok=0;
if(ar[i][0]>ar[i][1]){
swap(ar[i][0],ar[i][1]);
ok++;
}
int hm=Seg.query(1,1,p,mp[ar[i][0]],mp[ar[i][1]-1]);
ok+=query(1,1,k,hm+1,k,ar[i][1]);
if(ok&1) ans+=ar[i][1];
else ans+=ar[i][0];
}
cout << ans << endl;
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int t=1;//cin >> t;
while(t--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
21084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
21084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
21084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
