#include <bits/stdc++.h>
using namespace std;
const int mxn=2e5+5,sz=(1<<20);
int n,q,a[mxn],b[mxn],qu[mxn];
long long int ans=0;
struct segment{
vector<int>v[sz];
void build(int id,int L,int R){
if(L+1==R){
v[id].push_back(qu[L]);
return ;
}
int mid=(L+R)/2;
build(id*2,L,mid);
build(id*2+1,mid,R);
for(auto i:v[id*2])
v[id].push_back(i);
for(auto i:v[id*2+1])
v[id].push_back(i);
sort(v[id].begin(),v[id].end());
}
int get(int id,int L,int R,int l,int r){
if(L+1==R)
return L;
int mid=(L+R)/2;
int x=lower_bound(v[id].begin(),v[id].end(),l)-v[id].begin();
if(x==v[id].size() || v[id][x]>=r)
return 0;
x=lower_bound(v[id*2+1].begin(),v[id*2+1].end(),l)-v[id*2+1].begin();
if(x==v[id*2+1].size() || v[id*2+1][x]>=r)
return get(id*2,L,mid,l,r);
else
return get(id*2+1,mid,R,l,r);
}
int pet(int id,int L,int R,int l,int r,int x){
if(L==l && R==r){
int res=lower_bound(v[id].begin(),v[id].end(),x)-v[id].begin();
return v[id].size()-res;
}
int mid=(L+R)/2,res=0;
if(l<mid)
res+=pet(id*2,L,mid,l,min(r,mid),x);
if(r>mid)
res+=pet(id*2+1,mid,R,max(l,mid),r,x);
return res;
}
}seg;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
for(int i=1;i<=q;i++){
cin>>qu[i];
}
seg.build(1,1,q+1);
for(int i=1;i<=n;i++){
int x=min(a[i],b[i]);
int y=max(a[i],b[i]);
int l=seg.get(1,1,q+1,x,y);
int num=(l!=q)?seg.pet(1,1,q+1,l+1,q+1,y):0;
if(l==0)
ans+=(num&1)?b[i]:a[i];
else{
if(a[i]<b[i])
ans+=(num&1)?a[i]:b[i];
else
ans+=(num&1)?b[i]:a[i];
}
// cout<<ans<<" ";
}
cout<<ans<<endl;
}
Compilation message
cardgame2.cpp: In member function 'int segment::get(int, int, int, int, int)':
cardgame2.cpp:27:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | if(x==v[id].size() || v[id][x]>=r)
| ~^~~~~~~~~~~~~~
cardgame2.cpp:30:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | if(x==v[id*2+1].size() || v[id*2+1][x]>=r)
| ~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
27228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
27228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
27228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
