oj.uz

답안 #208359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208359 2020-03-11T01:39:01 Z YJU 운세 보기 2 (JOI14_fortune_telling2) C++14
0 / 100
 185 ms 262148 KB 
#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;
const ll INF=(1LL<<62);
#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 get(node *nd){return (!nd?0:nd->val);}

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(get(nd->rc),get(nd->lc));
}

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

ll ans,x[N],a[N],b[N],tt[N],lin[N],n,k;
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;
	}
	/*REP1(i,n){
		cout<<i<<" "<<lin[i]<<"\n";
	}*/
	reset(rt);
	for(ll i=k;i>=0;i--){
		for(auto j:v[i]){
			tt[j]=q(rt,max(a[i],b[i]),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?max(a[i],b[i]):min(a[i],b[i]));
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 185 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 185 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 185 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -