Submission #208361

#	Time	Username	Problem	Language	Result	Execution time	Memory
208361		YJU	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	1369 ms	183344 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=2e5+5;
const ld pi=3.14159265359;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

struct node{
	ll l,r,val,ti;
	node *lc,*rc;
}*rt=new node{0,MOD,0,0,0,0};

int getval(node *nd){return (!nd?0:nd->val);}

int getti(node *nd){return (!nd?0:nd->ti);}

void insert(node *nd,ll to,ll id){
	if(nd->l==nd->r-1){nd->val=max(nd->val,id);nd->ti++;return;}
	ll mid=(nd->l+nd->r)/2;
	if(to>=mid){
		if(!nd->rc)nd->rc=new node{mid,nd->r,0,0,0,0};
		insert(nd->rc,to,id);
	}else{
		if(!nd->lc)nd->lc=new node{nd->l,mid,0,0,0,0};
		insert(nd->lc,to,id);
	}
	nd->val=max(getval(nd->rc),getval(nd->lc));
	nd->ti=getti(nd->lc)+getti(nd->rc);
}

void reset(node *nd){
	if(!nd)return;
	if(nd->lc)reset(nd->lc);
	if(nd->rc)reset(nd->rc);
	nd->val=nd->ti=0;
}

ll x[N],a[N],b[N],tt[N],lin[N],n,k;
long long ans;
vector<ll> v[N];

ll q(node *nd,ll ql,ll qr,ll ty){
	if(!nd)return 0;
	if(nd->l>=ql&&nd->r<=qr){return (ty?nd->ti:nd->val);}
	if(nd->l>=qr||nd->r<=ql)return 0;
	if(ty){
		return q(nd->lc,ql,qr,ty)+q(nd->rc,ql,qr,ty);
	}else{
		return max(q(nd->lc,ql,qr,ty),q(nd->rc,ql,qr,ty));
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>k;
	REP1(i,n)cin>>a[i]>>b[i];
	REP1(i,k){
		cin>>x[i];
		insert(rt,x[i],i);
	}
	REP1(i,n){
		ll tmp=q(rt,min(a[i],b[i]),max(a[i],b[i]),0);
		v[tmp].pb(i);
		lin[i]=tmp;
	}
	reset(rt);
	for(ll i=k;i>=0;i--){
		for(auto j:v[i]){
			tt[j]=q(rt,max(a[j],b[j]),MOD,1);
		}
		insert(rt,x[i],i);
	}
	REP1(i,n){
		if(lin[i]==0){
			ans+=(tt[i]%2?b[i]:a[i]);
		}else{
			ans+=(tt[i]%2?min(a[i],b[i]):max(a[i],b[i]));
		}
	}
	cout<<ans<<"\n";
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65