Submission #285360

#	Time	Username	Problem	Language	Result	Execution time	Memory
285360		YJU	Pinball (JOI14_pinball)	C++14	100 / 100	365 ms	72560 KiB

pinball

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e6+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#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()
 
ll seg[2][4*N];
ll n,len,A[N],B[N],C[N],D[N],ans=INF,dpa,dpb;
vector<ll> lis;

void ins(ll ty,ll id,ll L,ll R,ll to,ll x){
	if(R-L==1){seg[ty][id]=min(seg[ty][id],x);return;}
	ll mid=(L+R)/2;
	if(to<mid){
		ins(ty,id*2,L,mid,to,x);
	}else{
		ins(ty,id*2+1,mid,R,to,x);
	}
	seg[ty][id]=min(seg[ty][id*2],seg[ty][id*2+1]);
}

ll query(ll ty,ll id,ll L,ll R,ll ql,ll qr){
	if(L>=qr||R<=ql)return INF;
	if(L>=ql&&R<=qr)return seg[ty][id];
	ll  mid=(L+R)/2;
	return min(query(ty,id*2,L,mid,ql,qr),query(ty,id*2+1,mid,R,ql,qr));
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>len;
	REP(i,n){
		cin>>A[i]>>B[i]>>C[i]>>D[i];
		lis.pb(A[i]);lis.pb(B[i]);lis.pb(C[i]);
	}
	lis.pb(1);lis.pb(len);
	sort(lis.begin(),lis.end());
	lis.resize(unique(lis.begin(),lis.end())-lis.begin());
	REP(i,n){
		A[i]=lwb(lis.begin(),lis.end(),A[i])-lis.begin();
		B[i]=lwb(lis.begin(),lis.end(),B[i])-lis.begin();
		C[i]=lwb(lis.begin(),lis.end(),C[i])-lis.begin();
	}
	
	len=SZ(lis);
	REP(i,2)REP(j,4*N)seg[i][j]=INF;
	ins(0,1,0,len,0,0);
	ins(1,1,0,len,len-1,0);
	REP(i,n){
		dpa=D[i]+query(0,1,0,len,A[i],B[i]+1);
		dpb=D[i]+query(1,1,0,len,A[i],B[i]+1);
		ans=min(ans,dpa+dpb-D[i]);
		ins(0,1,0,len,C[i],dpa);
		ins(1,1,0,len,C[i],dpb);
	}
	cout<<(ans>=INF?-1:ans)<<"\n";
	return 0;
}

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