#include <bits/stdc++.h>
using namespace std;
int n,m;
pair<int,int> a[200005];
pair<int,int> b[200005];
int t[3000005];
int tt[3000005];
long long ans;
int x,y;
int pos;
int xx;
int sz;
inline bool cmp(pair<int,int> x,pair<int,int> y) {
return max(x.first,x.second)<max(y.first,y.second);
}
inline void update(int x,int y) {
x+=sz-1;
t[x]++;
tt[x]=y;
x>>=1;
while (x) {
t[x]=t[x+x]+t[x+x+1];
tt[x]=max(tt[x+x],tt[x+x+1]);
x>>=1;
}
}
int get_pos(int l,int r,int x,int y) {
if (tt[x]<y) return 0;
int mid=(l+r)>>1;
int res=get_pos(mid+1,r,x+x+1,y);
if (!res) res=get_pos(l,mid,x+x,y);
return res;
}
int get_cnt(int l,int r,int ll,int rr,int x) {
if (l>r || ll>r || l>rr || ll>rr) return 0;
if (l>=ll && r<=rr) return t[x];
int mid=(l+r)>>1;
return get_cnt(l,mid,ll,rr,x+x)+get_cnt(mid+1,r,ll,rr,x+x+1);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m;
for (int i=1;i<=n;++i)
cin>>a[i].first>>a[i].second;
sort(a+1,a+n+1,cmp);
for (int i=1;i<=m;++i) {
cin>>b[i].first;
b[i].second=i;
}
sort(b+1,b+m+1);
int last=1;
sz=1;
while (sz<m) sz+=sz;
for (int i=1;i<=n;++i) {
x=max(a[i].first,a[i].second);
y=min(a[i].first,a[i].second);
if (x==y) {
ans+=x;
continue;
}
while (last<=m && b[last].first<x) {
update(b[last].second,b[last].first);
++last;
}
pos=get_pos(1,sz,1,y)+1;
xx=get_cnt(1,sz,pos,m,1);
xx=m-pos+1-xx;
xx%=2;
if (xx) ans+=x;
else ans+=y;
}
cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
