oj.uz

답안 #19178

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19178 2016-02-19T13:06:51 Z comet Pinball (JOI14_pinball) C++
100 / 100
 202 ms 24912 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[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.0 / 11.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 24912 KB Output is correct
2 Correct 39 ms 24912 KB Output is correct
3 Correct 125 ms 24912 KB Output is correct
4 Correct 128 ms 24912 KB Output is correct
5 Correct 88 ms 24912 KB Output is correct
6 Correct 178 ms 24912 KB Output is correct
7 Correct 202 ms 24912 KB Output is correct
8 Correct 198 ms 24912 KB Output is correct
9 Correct 29 ms 24912 KB Output is correct
10 Correct 88 ms 24912 KB Output is correct
11 Correct 130 ms 24912 KB Output is correct
12 Correct 191 ms 24912 KB Output is correct
13 Correct 168 ms 24912 KB Output is correct
14 Correct 160 ms 24912 KB Output is correct