Submission #845994

#TimeUsernameProblemLanguageResultExecution timeMemory
845994dungzFortune Telling 2 (JOI14_fortune_telling2)C++17
100 / 100
1193 ms141560 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...