#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=200010, inf=2e9;
int n, k;
int Q[MX];
pii C[MX];
int tree[MX*4];
void upt(int v, int s, int e, int x){
if(x<s || e<x) return;
if(s==e){
tree[v]++;
return;
}
upt(v*2,s,(s+e)/2,x);
upt(v*2+1,(s+e)/2+1,e,x);
tree[v]=tree[v*2]+tree[v*2+1];
}
int cnt(int v, int s, int e, int l, int r){
if(e<l || r<s) return 0;
if(l<=s && e<=r) return tree[v];
return cnt(v*2,s,(s+e)/2,l,r) + cnt(v*2+1,(s+e)/2+1,e,l,r);
}
int cnt(int l, int r){
if(l>r) return 0;
return cnt(1,1,k,l,r);
}
ll solve(){
ll ans=0;
int mn[MX]={};
mn[k]=Q[k];
for(int i=k-1; i>0; i--){
mn[i]=min(mn[i+1], Q[i]);
}
sort(C+1, C+n+1, [](pii &a, pii &b){
return max(a.first, a.second)>max(b.first, b.second);
});
int idx[MX];
iota(idx, idx+k+1, 0);
sort(idx+1, idx+k+1, [](int a, int b){
return Q[a]>Q[b];
});
for(int i=1, pos=1, l=k+1; i<=n; i++){
int x, y; tie(x,y)=C[i];
if(x>y) swap(x,y);
if(x==y){
ans+=x;
continue;
}
while(pos<=k && Q[idx[pos]]>=y){
upt(1,1,k,idx[pos]);
pos++;
// cout<<i<<" UPT!\n";
}
while(l>1 && mn[l-1]>=y) l--;
// printf("(%d, %d): %d~%d, %d: %d\n", x, y, l, k, pos-1, cnt(l,k));
// ll old=ans;
if(l==1 || mn[l-1]<x){
ans+= (cnt(l, k)%2==1 ? C[i].second : C[i].first);
}
else{
ans+= (cnt(l, k)%2==1 ? x : y);
}
// cout<<ans-old<<'\n';
}
return ans;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>k;
for(int i=1, a, b; i<=n; i++){
cin>>a>>b;
C[i]={a,b};
}
for(int i=1; i<=k; i++){
cin>>Q[i];
}
cout<<solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
