Submission #19178

#	Time	Username	Problem	Language	Result	Execution time	Memory
19178		comet	Pinball (JOI14_pinball)	C++98	100 / 100	202 ms	24912 KiB

pinball

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;

int N,M;
struct obs{
	int L,R;
	int G;
	ll C;
}a[100010];
int lu[300010];
ll dp_L[100010],dp_R[100010];

void compress(){
	lu[0]=1;
	lu[1]=M;
	M=2;
	for(int i=0;i<N;i++){
		lu[M++]=a[i].L;
		lu[M++]=a[i].R;
		lu[M++]=a[i].G;
	}
	sort(lu,lu+M);
	M=unique(lu,lu+M)-lu;
	for(int i=0;i<N;i++){
		a[i].L=lower_bound(lu,lu+M,a[i].L)-lu;
		a[i].R=lower_bound(lu,lu+M,a[i].R)-lu;
		a[i].G=lower_bound(lu,lu+M,a[i].G)-lu;
	}
}

void input(){
	scanf("%d%d",&N,&M);
	for(int i=0;i<N;i++){
		scanf("%d%d%d%lld",&a[i].L,&a[i].R,&a[i].G,&a[i].C);
	}
}

ll tree_L[1200000],tree_R[1200000];
int sz;

void init(){
	compress();
	for(sz=1;sz<M;sz<<=1);
	for(int i=0;i<=sz+M;i++){
		tree_L[i]=tree_R[i]=1e18;
	}
}

void update(ll tree[],int x,ll c){
	x+=sz;
	tree[x]=min(tree[x],c);
	x>>=1;
	while(x){
		tree[x]=min(tree[x*2],tree[x*2+1]);
		x>>=1;
	}
}

ll query(ll tree[],int L,int R){
	L+=sz,R+=sz;
	ll ret=1e18;
	while(L<R){
		if(L&1)ret=min(ret,tree[L++]);
		if(~R&1)ret=min(ret,tree[R--]);
		L>>=1,R>>=1;
	}
	if(L==R){
		ret=min(ret,tree[L]);
	}
	return ret;
}

void PS(){
	
	init();

	for(int i=0;i<N;i++){
		dp_L[i]=dp_R[i]=1e18;
		if(a[i].L==0){
			dp_L[i]=a[i].C;
		}
		if(a[i].R==M-1){
			dp_R[i]=a[i].C;
		}
		dp_L[i]=min(dp_L[i],query(tree_L,a[i].L,a[i].R)+a[i].C);
		dp_R[i]=min(dp_R[i],query(tree_R,a[i].L,a[i].R)+a[i].C);
		update(tree_L,a[i].G,dp_L[i]);
		update(tree_R,a[i].G,dp_R[i]);
	}

	ll ans=1e18;
	for(int i=0;i<N;i++){
		ans=min(ans,dp_L[i]+dp_R[i]-a[i].C);
	}
	if(ans==1e18){
		puts("-1");
	}else{
		printf("%lld\n",ans);
	}
}

int main(){

	input();
	PS();
	return 0;

}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49