Submission #1166897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166897		_rain_	Pinball (JOI14_pinball)	C++20	100 / 100	152 ms	22032 KiB

pinball

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=1e5;
int num_dev,n;
int a[N+2],b[N+2],c[N+2],d[N+2];
int start_point,end_point;
vector<int>nen;

int Find(vector<int>&x,int val){
	return upper_bound(x.begin(),x.end(),val)-x.begin();
}

void compress(){
	nen.push_back(1),nen.push_back(n);
	for(int i=1;i<=num_dev;++i) {
		nen.push_back(a[i]);
		nen.push_back(c[i]);
		nen.push_back(b[i]);
	}
	sort(nen.begin(),nen.end());
	nen.resize(unique(nen.begin(),nen.end())-nen.begin());
	for(int i=1;i<=num_dev;++i){
		a[i]=Find(nen,a[i]);
		b[i]=Find(nen,b[i]);
		c[i]=Find(nen,c[i]);
	}
	start_point=Find(nen,1);
	end_point=Find(nen,n);
	return;
}
const LL INF=(LL)1e18;

class IT{
	public:
		vector<LL>st;
		#define lef(id) id*2
		#define rig(id) id*2+1
		void init(int _n){
			st.assign(_n*4+2,INF);
		}
		
		void upd(int id,int l,int r,int pos,LL val){
			if (l>pos||r<pos) return;
			if (l==r) st[id]=min(st[id],val);
			else{
				int m=(l+r)/2;
				upd(lef(id),l,m,pos,val);
				upd(rig(id),m+1,r,pos,val);
				st[id]=min(st[lef(id)],st[rig(id)]);
			}
		}
		LL get(int id,int l,int r,int u,int v){
			if (l>v||r<u) return INF;
			if (u<=l&&r<=v) return st[id];
			int m=(l+r)/2;
			return min(get(lef(id),l,m,u,v),get(rig(id),m+1,r,u,v));
		}
};
#define left asdasd
#define right asdasdd
IT left,right;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	
	
	cin>>num_dev>>n;

	for(int i=1;i<=num_dev;++i){
		cin>>a[i]>>b[i]>>c[i]>>d[i];
	}
	compress();
	left.init(nen.size()),right.init(nen.size());
	LL ans=INF;
	left.upd(1,1,nen.size(),start_point,0);
	right.upd(1,1,nen.size(),end_point,0);
	for(int i=1;i<=num_dev;++i){
		LL lef=left.get(1,1,nen.size(),a[i],b[i]);
		LL rig=right.get(1,1,nen.size(),a[i],b[i]);
		ans=min(ans,lef+rig+d[i]);
		left.upd(1,1,nen.size(),c[i],lef+d[i]);
		right.upd(1,1,nen.size(),c[i],rig+d[i]);
	}
	cout<<(ans==INF?-1:ans);
}

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