This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "swapcard"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
#define int ll
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7;
vector<int> f[800005];
int tree[3000005];
map<ll,int> danh;
int d=0;
pair<ll,ll> a[200005];
ll t[200005];
ll rev[1000005];
void build(ll node,ll l,ll r){
if(l==r) {f[node].push_back(t[l]);return;}
ll m=(l+r)/2;
build(node*2,l,m);
build(node*2+1,m+1,r);
merge(f[node*2].begin(),f[node*2].end(),f[node*2+1].begin(),f[node*2+1].end(),back_inserter(f[node]));
}
ll chat(ll node,ll x){
ll l=0,r=f[node].size()-1,fl=-1;
while(l<=r){
ll m=(l+r)/2;
if(f[node][m]>=x){
fl=m;
r=m-1;
}
else l=m+1;
}
return (fl==-1?0:f[node].size()-fl);
}
ll get(ll node,ll l,ll r,ll u,ll v,ll x){
if(l>v or r<u) return 0;
if(l>=u and r<=v) return chat(node,x);
ll m=(l+r)/2;
return get(node*2,l,m,u,v,x)+get(node*2+1,m+1,r,u,v,x);
}
void update2(int node,int l,int r,int u,int v)
{
if(l>u or r<u) return;
if(l==r)
{
tree[node]=v;
return;
}
int m=(l+r)/2;
update2(node*2,l,m,u,v);
update2(node*2+1,m+1,r,u,v);
tree[node]=max(tree[node*2],tree[node*2+1]);
}
int get2(int node,int l ,int r ,int u, int v)
{
if(l>v or r<u) return -1;
if(l>=u and r<=v) return tree[node];
int m=(l+r)/2;
return max(get2(node*2,l,m,u,v),get2(node*2+1,m+1,r,u,v));
}
vector<ll> lst;
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i].fi>>a[i].se;
lst.push_back(a[i].fi);
lst.push_back(a[i].se);
}
for(int i=1;i<=k;i++)
{
cin>>t[i];
lst.push_back(t[i]);
}
sort(lst.begin(),lst.end());
for(auto i:lst)
{
if(!danh[i])
{
danh[i]=++d;
rev[d]=i;
}
}
for(int i=1;i<=n;i++)
{
a[i].fi=danh[a[i].fi];
a[i].se=danh[a[i].se];
}
for(int i=1;i<=4*d;i++)
{
tree[i]=-1;
}
for(int i=1;i<=k;i++)
{
t[i]=danh[t[i]];
update2(1,1,d,t[i],i);
}
build(1,1,k);
ll ans=0;
for(int i=1;i<=n;i++)
{
int u=a[i].fi,v=a[i].se;
if(u>v) swap(u,v);
int pos=get2(1,1,d,u,v-1);
// cout<<u<<" "<<v<<" "<<pos<<endl;
if(pos==-1)
{
int sl=get(1,1,k,1,k,v);
if(sl%2==0) ans+=rev[a[i].fi];
else ans+=rev[a[i].se];
// if(sl%2==0) cout<<a[i].fi<<endl;
// else cout<<a[i].se;
}
else
{
int sl=get(1,1,k,pos,k,v);
if(sl%2==0) ans+=rev[v];
else ans+=rev[u];
// if(sl%2==0) cout<<u<<endl;
// else cout<<u<<endl;
}
// cout<<endl;
}
cout<<ans;
}
/*
*/
Compilation message (stderr)
fortune_telling2.cpp:9: warning: "task" redefined
9 | #define task "swapcard"
|
fortune_telling2.cpp:8: note: this is the location of the previous definition
8 | #define task "task"
|
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |