#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
const int MAXM=6e5+6;
const int INF=2e9;
map<int,int>mp;
set<int>xs;
int n,k;
int t[MAXN],a[MAXN],b[MAXN];
bool cmp(pair<int,int> p1,pair<int,int>p2)
{
return make_pair(max(p1.first,p1.second),min(p1.first,p1.second))>make_pair(max(p2.first,p2.second),min(p2.first,p2.second));
}
vector<pair<int,int> >v;
struct segment_tree
{
int tree[4*MAXM];
void init()
{
memset(tree,0,sizeof(tree));
}
void update(int l,int r,int q,int idx,int val)
{
if(l>q)return;
if(r<q)return;
if(l==r)
{
tree[idx]=max(tree[idx],val);
return;
}
int mid=(l+r)/2;
update(l,mid,q,idx*2,val);
update(mid+1,r,q,idx*2+1,val);
}
int query(int l,int r,int idx,int ql,int qr)
{
if(ql>qr)return 0;
if(l>qr||r<ql)return 0;
if(l>=ql&&r<=qr)return tree[idx];
int mid=(l+r)/2;
return max(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
}
}ivan;
struct BIT
{
int fen[MAXM];
void update(int idx,int val)
{
idx++;
for(;idx<MAXM;idx+=idx&(-idx))
{
fen[idx]+=val;
}
}
int query(int idx)
{
idx++;
int ret=0;
for(;idx>0;idx-=idx&(-idx))
{
ret+=fen[idx];
}
return ret;
}
int query(int l,int r)
{
return query(r)-query(l-1);
}
}vanka;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
xs.insert(a[i]);
xs.insert(b[i]);
v.push_back({a[i],b[i]});
}
sort(v.begin(),v.end(),cmp);
for(int i=1;i<=k;i++)
{
cin>>t[i];
xs.insert(t[i]);
}
xs.insert(INF);
int cnt=0;
for(auto xd:xs)
{
cnt++;
mp[xd]=cnt;
}
vector<pair<int,int> >v1;
ivan.init();
int ans=0;
for(int i=1;i<=k;i++)
{
v1.push_back({t[i],i});
ivan.update(1,cnt,mp[t[i]],1,i);
}
sort(v1.begin(),v1.end());
int r=v1.size()-1;
for(int i=0;i<v.size();i++)
{
while(r>=0&&v1[r].first>=max(v[i].first,v[i].second))
{
//cout<<"*\n";
vanka.update(v1[r].second,+1);
r--;
}
int lastxd=ivan.query(1,cnt,1,mp[min(v[i].first,v[i].second)],mp[max(v[i].first,v[i].second)]-1);
//cout<<lastxd<<endl;
if(lastxd==0)
{
int f=vanka.query(1,k);
//cout<<f<<endl;
if(f%2==1)ans+=v[i].second;
else ans+=v[i].first;
}
else
{
int f=vanka.query(lastxd+1,k);
if(f%2==0)
{
ans+=max(v[i].first,v[i].second);
}
else
{
ans+=min(v[i].first,v[i].second);
}
}
//cout<<v[i].first<<" "<<v[i].second<<" "<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:103:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
