Submission #340214

#	Time	Username	Problem	Language	Result	Execution time	Memory
340214		Bill_00	Pinball (JOI14_pinball)	C++14	0 / 100	1 ms	492 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 1e9
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;
	inline 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;
	}

	inline 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) le=new node();
		if(ri==NULL) ri=new node();
		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];
	}
	ll lll=1,rrr=n;
	L=R=1;
	seg1->update(0,1,n);
	L=R=n;
	seg2->update(0,1,n);
	for(int i=1;i<=m;++i){
		ll cost1=MAX,cost2=MAX;
		if(lll>=a[i]){
			L=a[i],R=b[i];
			cost1=(seg1->query(1,n));
			if(cost1!=MAX){
				L=R=c[i];
				seg1->update(cost1+d[i],1,n);
				lll=max(lll,c[i]);
			}
		}
		if(rrr<=b[i]){
			L=a[i],R=b[i];
			cost2=(seg2->query(1,n));
			if(cost2!=MAX){
				L=R=c[i];
				seg2->update(cost2+d[i],1,n);
				rrr=min(rrr,c[i]);
			}
		}
		if(cost1!=MAX && cost2!=MAX){
			ans=min(ans,cost1+cost2+d[i]);
		}
	}
	if(ans==MAX) cout << -1;
	else cout << ans;
}

Compilation message (stderr)

pinball.cpp: In member function 'void node::update(ll, ll, ll)':
pinball.cpp:30:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   ll m=l+r>>1;
      |        ~^~
pinball.cpp: In member function 'll node::query(ll, ll)':
pinball.cpp:56:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |   ll m=l+r>>1;
      |        ~^~

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