Submission #165206

#	Time	Username	Problem	Language	Result	Execution time	Memory
165206		TAISA_	Pinball (JOI14_pinball)	C++14	100 / 100	290 ms	26480 KiB

pinball

#include<bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
using namespace std;
using ll=long long;
const ll LINF=(1LL<<60)-1LL;
struct Segtree{
	int n;
	vector<ll> dat;
	Segtree(int n_){
		n=1;
		while(n<n_){
			n<<=1;
		}
		dat.resize(2*n,LINF);
	}
	void upd(int k,ll x){
		k+=n;
		dat[k]=min(dat[k],x);
		k>>=1;
		while(k>0){
			dat[k]=min(dat[k<<1],dat[k<<1|1]);
			k>>=1;
		}
	}
	ll get(int a,int b,int k,int l,int r){
		if(b<=l||r<=a){
			return LINF;
		}
		if(a<=l&&r<=b){
			return dat[k];
		}
		return min(get(a,b,k<<1,l,(l+r)>>1),get(a,b,k<<1|1,(l+r)>>1,r));
	}
	ll get(int a,int b){
		return get(a,b,1,0,n);
	}
};
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int m,nn;cin>>m>>nn;
	vector<ll> a(m),b(m),c(m),d(m),v;
	for(int i=0;i<m;i++){
		cin>>a[i]>>b[i]>>c[i]>>d[i];
		v.push_back(a[i]);
		v.push_back(b[i]);
		v.push_back(c[i]);
	}
	v.push_back(1);
	v.push_back(nn);
	sort(all(v));
	v.erase(unique(all(v)),v.end());
	int n=v.size();
	for(int i=0;i<m;i++){
		a[i]=lower_bound(all(v),a[i])-v.begin();
		b[i]=lower_bound(all(v),b[i])-v.begin();
		c[i]=lower_bound(all(v),c[i])-v.begin();
	}
	ll res=LINF;
	Segtree seg1(n+1),seg2(n+1);
	seg1.upd(0,0);
	seg2.upd(n-1,0);
	for(int i=0;i<m;i++){
		ll s1=seg1.get(a[i],b[i]+1),s2=seg2.get(a[i],b[i]+1);
		s1+=d[i];
		s2+=d[i];
		res=min(res,s1+s2-d[i]);
		seg1.upd(c[i],s1);
		seg2.upd(c[i],s2);
	}
	if(res==LINF){
		cout<<-1<<endl;
		return 0;
	}
	cout<<res<<endl;
}	

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