oj.uz

답안 #29071

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29071 2017-07-18T08:02:44 Z PrOAhMeT Pinball (JOI14_pinball) C++14
100 / 100
 606 ms 79524 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXNODE=100000*33;
int n,m,cl[MAXNODE],cr[MAXNODE],tme=1,a,b,c,d,one;
LL f[2][MAXNODE],ans=1e16;

void upd(int &x,int l,int r,int ll,LL val,int d) {

	if(x==0) {
		x=++tme;
		f[0][x]=f[1][x]=1e16;
	}
	if(l==ll&&r==ll) {
		f[d][x]=min(f[d][x],val);
		return;
	}
	int md=(l+r)/2;
	if(ll<=md)
		upd(cl[x],l,md,ll,val,d);
	else upd(cr[x],md+1,r,ll,val,d);
	f[d][x]=min(cl[x]==0?1e17:f[d][cl[x]],cr[x]==0?1e17:f[d][cr[x]]);

}

LL que(int x,int l,int r,int ll,int rr,int d) {

	if(x==0)
		return 1e16;
	if(l>rr||r<ll)
		return 1e16;
	if(l>=ll&&r<=rr)
		return f[d][x];
	int md=(l+r)/2;
	return min(que(cl[x],l,md,ll,rr,d),que(cr[x],md+1,r,ll,rr,d));

}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	f[0][1]=f[1][1]=1e16;
	for(int i=0;i<n;++i) {
		cin>>a>>b>>c>>d;
		LL left=que(1,1,m,a,b,0);
		if(a==1) left=0;
		LL right=que(1,1,m,a,b,1);
		if(b==m) right=0;
		ans=min(ans,left+right+d);
		one=1;
		upd(one,1,m,c,left+d,0);
		one=1;
		upd(one,1,m,c,right+d,1);
	}
	if(ans==1e16)
		cout<<-1<<endl;
	else cout<<ans<<endl;

}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 79524 KB Output is correct
2 Correct 93 ms 79524 KB Output is correct
3 Correct 323 ms 79524 KB Output is correct
4 Correct 366 ms 79524 KB Output is correct
5 Correct 229 ms 79524 KB Output is correct
6 Correct 463 ms 79524 KB Output is correct
7 Correct 606 ms 79524 KB Output is correct
8 Correct 583 ms 79524 KB Output is correct
9 Correct 39 ms 79524 KB Output is correct
10 Correct 233 ms 79524 KB Output is correct
11 Correct 259 ms 79524 KB Output is correct
12 Correct 503 ms 79524 KB Output is correct
13 Correct 419 ms 79524 KB Output is correct
14 Correct 353 ms 79524 KB Output is correct