oj.uz

답안 #19177

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19177 2016-02-19T13:00:32 Z comet Pinball (JOI14_pinball) C++
18 / 100
 122 ms 24128 KB 
#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[100010];
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],sz;

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

void update(ll tree[],int x,ll c){
	x+=sz;
	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
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 24128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 24128 KB Output is correct
2 Correct 0 ms 24128 KB Output is correct
3 Correct 1 ms 24128 KB Output is correct
4 Correct 0 ms 24128 KB Output is correct
5 Correct 0 ms 24128 KB Output is correct
6 Correct 0 ms 24128 KB Output is correct

Subtask #3
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 24128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 24128 KB Output is correct
2 Correct 48 ms 24128 KB Output is correct
3 Incorrect 122 ms 24128 KB Output isn't correct
4 Halted 0 ms 0 KB -