#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define N 200001
typedef long long ll;
const long long MOD=1000000007;
using namespace std;
int n,k;
int a[N],b[N],mx[4*N+4];
pair<int,int>t[N];
vector<int>v[4*N+4];
void build(int id,int l,int r){
if(l==r){
v[id].pb(t[l].ss);
mx[id]=t[l].ss;
return;
}
int m=l+r>>1;
build(id*2,l,m);
build(id*2+1,m+1,r);
mx[id]=max(mx[id*2],mx[id*2+1]);
int i=0,j=0;
while(i<v[id*2].size() && j<v[id*2+1].size()){
if(v[id*2][i]<v[id*2+1][j]){
v[id].pb(v[id*2][i]);
i++;
}
else{
v[id].pb(v[id*2+1][j]);
j++;
}
}
while(i<v[id*2].size()){
v[id].pb(v[id*2][i]);
i++;
}
while(j<v[id*2+1].size()){
v[id].pb(v[id*2+1][j]);
j++;
}
}
int query1(int id,int l,int r,int L,int R){
if(r<L || R<l) return 0;
if(L<=l && r<=R) return mx[id];
int m=l+r>>1;
return max(query1(id*2,l,m,L,R),query1(id*2+1,m+1,r,L,R));
}
int query2(int id,int l,int r,int L,int R,int k){
if(r<L || R<l) return 0;
if(L<=l && r<=R) return v[id].size()-(upper_bound(v[id].begin(),v[id].end(),k)-v[id].begin());
int m=l+r>>1;
return (query2(id*2,l,m,L,R,k)+query2(id*2+1,m+1,r,L,R,k));
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for(int i=1;i<=n;i++){
cin >> a[i] >> b[i];
}
for(int i=1;i<=k;i++){
cin >> t[i].ff;
t[i].ss=i;
}
sort(t+1,t+k+1);
build(1,1,k);
ll ans=0;
for(int i=1;i<=n;i++){
pair<int,int>temp={min(a[i],b[i]),0};
int l=(lower_bound(t+1,t+k+1,temp)-(t+1));
l++;
temp={max(a[i],b[i]),0};
int r=(lower_bound(t+1,t+k+1,temp)-(t+1));
if(l>r){
ans+=(ll)(((n-r)%2)?b[i]:a[i]);
}
else{
int p=query1(1,1,k,l,r);
int u=query2(1,1,k,r+1,n,p);
ans+=(ll)((u%2)?min(a[i],b[i]):max(a[i],b[i]));
}
}
cout << ans;
}
Compilation message
fortune_telling2.cpp: In function 'void build(int, int, int)':
fortune_telling2.cpp:19:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
19 | int m=l+r>>1;
| ~^~
fortune_telling2.cpp:24:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | while(i<v[id*2].size() && j<v[id*2+1].size()){
| ~^~~~~~~~~~~~~~~
fortune_telling2.cpp:24:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | while(i<v[id*2].size() && j<v[id*2+1].size()){
| ~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:34:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while(i<v[id*2].size()){
| ~^~~~~~~~~~~~~~~
fortune_telling2.cpp:38:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | while(j<v[id*2+1].size()){
| ~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int query1(int, int, int, int, int)':
fortune_telling2.cpp:46:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int m=l+r>>1;
| ~^~
fortune_telling2.cpp: In function 'int query2(int, int, int, int, int, int)':
fortune_telling2.cpp:52:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int m=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
19308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
19308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
19308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
