Submission #340249

#	Time	Username	Problem	Language	Result	Execution time	Memory
340249		Bill_00	Pinball (JOI14_pinball)	C++14	100 / 100	745 ms	179308 KiB

pinball

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define M 100005
#define MAX 1e18
typedef long long ll; 
using namespace std;
ll m,n,L,R,ans=MAX;
ll a[M],b[M];
ll c[M],d[M];
 
struct node{
	bool vis;
	ll mn;
	node *le,*ri;
	void update(ll up,ll l,ll r){
		if(r<L || R<l) return;
		if(L<=l && r<=R){
			if(vis){
				mn=min(mn,up);
			}
			else mn=up;
			vis=1;
			return;
		}
		if(le==NULL) le=new node();
		if(ri==NULL) ri=new node();
		ll m=(l+r)>>1;
		le->update(up,l,m);
		ri->update(up,m+1,r);
		if(!(le->vis)){
			mn=ri->mn;
			vis=1;
			return;
		}
		if(!(ri->vis)){
			mn=le->mn;
			vis=1;
			return;
		}
		mn=min((le->mn),(ri->mn));
		vis=1;
		return;
	}
 
	ll query(ll l,ll r){
		if(r<L || R<l) return MAX;
		if(L<=l && r<=R){
			if(vis) return mn;
			else return MAX;
		}
		if(le==NULL) return MAX;
		if(ri==NULL) return MAX;
		ll m=(l+r)>>1;
		return min((le->query(l,m)),(ri->query(m+1,r)));
	}
 
} *seg1=new node(),*seg2=new node();
 
 
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> m >> n;
	for(int i=1;i<=m;++i){
		cin >> a[i] >> b[i];
		cin >> c[i] >> d[i];
	}
	L=R=1;
	seg1->update(0,1,n);
	L=R=n;
	seg2->update(0,1,n);
	for(int i=1;i<=m;++i){
		L=a[i],R=b[i];
		ll cost1=(seg1->query(1,n));
		ll cost2=(seg2->query(1,n));
		if(cost1!=MAX && cost2!=MAX){
			ans=min(ans,cost1+cost2+d[i]);
		}
		L=R=c[i];
		if(cost1!=MAX){
			seg1->update(cost1+d[i],1,n);
		}
		if(cost2!=MAX){
			seg2->update(cost2+d[i],1,n);
		}
	}
	if(ans==MAX) cout << -1;
	else cout << ans;
}

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