#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+6;
const ll MAXM=6e5+6;
const ll INF=2e9;
map<ll,ll>mp;
set<ll>xs;
ll n,k;
ll t[MAXN],a[MAXN],b[MAXN];
bool cmp(pair<ll,ll> p1,pair<ll,ll>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<ll,ll> >v;
struct segment_tree
{
ll tree[4*MAXM];
void init()
{
memset(tree,0,sizeof(tree));
}
void update(ll l,ll r,ll q,ll idx,ll val)
{
if(l>q)return;
if(r<q)return;
if(l==r)
{
tree[idx]=max(tree[idx],val);
return;
}
ll mid=(l+r)/2;
update(l,mid,q,idx*2,val);
update(mid+1,r,q,idx*2+1,val);
}
ll query(ll l,ll r,ll idx,ll ql,ll qr)
{
if(ql>qr)return 0;
if(l>qr||r<ql)return 0;
if(l>=ql&&r<=qr)return tree[idx];
ll 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
{
ll fen[MAXM];
void init()
{
memset(fen,0,sizeof(fen));
}
void update(ll idx,ll val)
{
idx++;
for(;idx<MAXM;idx+=idx&(-idx))
{
fen[idx]+=val;
}
}
ll query(ll idx)
{
idx++;
ll ret=0;
for(;idx>0;idx-=idx&(-idx))
{
ret+=fen[idx];
}
return ret;
}
ll query(ll l,ll r)
{
return query(r)-query(l-1);
}
}vanka;
int main()
{
cin>>n>>k;
for(ll 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(ll i=1;i<=k;i++)
{
cin>>t[i];
xs.insert(t[i]);
}
xs.insert(INF);
ll cnt=0;
for(auto xd:xs)
{
cnt++;
mp[xd]=cnt;
}
vector<pair<ll,ll> >v1;
ivan.init();vanka.init();
ll ans=0,ans1=0;
for(ll 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());
ll r=v1.size()-1;
for(ll 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--;
}
ll 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)
{
ll f=vanka.query(1,k);
//cout<<f<<endl;
if(f%2==1)ans+=v[i].second;
else ans+=v[i].first;
}
else
{
ll 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;
}
for(int i=1;i<=n;i++)
{
int cnt1=0;
for(int j=k;j>=0;j--)
{
if(j==0)
{
if(cnt1%2==0)ans1+=a[i];
else ans1+=b[i];
break;
}
if(t[j]>=max(a[i],b[i]))cnt1++;
if(t[j]>=min(a[i],b[i])&&t[j]<max(a[i],b[i]))
{
if(cnt1%2==0)ans1+=max(a[i],b[i]);
else ans1+=min(a[i],b[i]);
break;
}
}
}
if(ans1!=ans)assert(false);
cout<<ans1<<endl;
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:108:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(ll i=0;i<v.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
48332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
48332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
48332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
