Submission #231000

#	Time	Username	Problem	Language	Result	Execution time	Memory
231000		kshitij_sodani	Pinball (JOI14_pinball)	C++17	100 / 100	285 ms	16400 KiB

pinball

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define a first
#define b second
#define pb push_back
llo n,m;
llo ac,bc,cd,dd;
llo tree[400001];
llo ma=1000000000000000000;
llo query(llo no,llo l,llo r,llo aa,llo bb){
	if(l>r or l>bb or r<aa){
		return ma;
	}
	if(aa<=l and r<=bb){
		return tree[no];
	}
	else{
		llo mid=(l+r)/2;
		return min(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
	}
}
void update(llo no,llo l,llo r,llo i,llo val){
	if(i<l or i>r){
		return;
	}
	if(l==r and l==i){
		tree[no]=val;
	}
	else{
		llo mid=(l+r)/2;
		update(no*2+1,l,mid,i,val);
		update(no*2+2,mid+1,r,i,val);
		tree[no]=min(tree[no*2+1],tree[no*2+2]);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
//	memset(tree,ma,sizeof(tree));
	cin>>m>>n;
	for(int i=0;i<4*m+1;i++){
		tree[i]=ma;
	}
	pair<llo,llo> aa[m];
	vector<pair<llo,llo>> bb;
	vector<pair<llo,llo>> cc;

	for(llo i=0;i<m;i++){
		cin>>ac>>bc>>cd>>dd;
		//aa.pb({cd,i});
		aa[i]={cd,i};
		bb.pb({ac,bc});
		cc.pb({cd,dd});
	}
	llo ind[m];
	sort(aa,aa+m);
	for(llo i=0;i<m;i++){
		ind[aa[i].b]=i;
	}
	pair<llo,llo> cost[m];
	pair<llo,llo> cost2[m];
//	cout<<tree[0]<<endl;
	for(llo i=0;i<m;i++){
		if(bb[i].a==1){
			update(0,0,m-1,ind[i],cc[i].b);
			cost[i]={0,cc[i].b};
		}
		else{
		//	cout<<lower_bound(aa,aa+m,mp(bb[i].a,(llo)0))-aa<<" "<<lower_bound(aa,aa+m,mp(bb[i].b+1,(llo)0))-aa-1<<endl;
			llo x=query(0,0,m-1,lower_bound(aa,aa+m,mp(bb[i].a,(llo)0))-aa,lower_bound(aa,aa+m,mp(bb[i].b+1,(llo)0))-aa-1);
			//cout<<x<<endl;
			update(0,0,m-1,ind[i],x+cc[i].b);
			cost[i]={x,cc[i].b};
		}
	}
	for(int i=0;i<4*m+1;i++){
		tree[i]=ma;
	}
	for(llo i=0;i<m;i++){
		if(bb[i].b==n){
			update(0,0,m-1,ind[i],cc[i].b);
			cost2[i]={0,cc[i].b};
		}
		else{
			llo x=query(0,0,m-1,lower_bound(aa,aa+m,mp(bb[i].a,(llo)0))-aa,lower_bound(aa,aa+m,mp(bb[i].b+1,(llo)0))-aa-1);
			update(0,0,m-1,ind[i],x+cc[i].b);
			cost2[i]={x,cc[i].b};
		}
	}
	llo ans=ma;
	llo st=0;
	/*for(llo i=0;i<m;i++){
		cout<<cost[i].a<<","<<cost[i].b<<endl;
	}

	for(llo i=0;i<m;i++){
		cout<<cost2[i].a<<":"<<cost2[i].b<<endl;
	}*/
	for(llo i=0;i<m;i++){
	
		ans=min(ans,(cost[i].a+cost2[i].a+cost[i].b));
	}
	if(ans>=ma){
		cout<<-1<<endl;
		return 0;
	}
	cout<<ans<<endl;













	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:94:6: warning: unused variable 'st' [-Wunused-variable]
  llo st=0;
      ^~

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