Submission #975578

#	Time	Username	Problem	Language	Result	Execution time	Memory
975578		PM1	Pinball (JOI14_pinball)	C++17	100 / 100	268 ms	33476 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=1e5+5,sz=(1<<20);
ll n,m,g[mxn][4];
vector<int>v;
struct segment{
	ll mn[sz];
	void up(int id,int L,int R,int l,ll x,bool w){
		if(L+1==R){
			if(w==1 || mn[id]>x){
				mn[id]=x;
			}
			return;
		}
		int mid=(L+R)/2;
		if(l<mid)
			up(id*2,L,mid,l,x,w);
		else
			up(id*2+1,mid,R,l,x,w);
		if(mn[id*2]<mn[id*2+1])
			mn[id]=mn[id*2];
		else
			mn[id]=mn[id*2+1];
	}
	ll get(int id,int L,int R,int l,int r){
		if(L==l && R==r){
			return mn[id];
		}
		ll x1=1e16,x2=1e16;
		int mid=(L+R)/2;
		if(l<mid)
			x1=get(id*2,L,mid,l,min(r,mid));
		if(r>mid)
			x2=get(id*2+1,mid,R,max(l,mid),r);
		return min(x1,x2);
	}
}seg[3];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=0;j<3;j++){
			cin>>g[i][j];
			v.push_back(g[i][j]);
		}
		cin>>g[i][3];
	}
	if(n==1){
		cout<<0;
		return 0;
	}
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end())-v.begin());
	for(int i=1;i<=m;i++){
		for(int j=0;j<3;j++){
			int x=lower_bound(v.begin(),v.end(),g[i][j])-v.begin();
			g[i][j]=x;
		}
	}
	if(v.back()!=n || v[0]!=1){
		cout<<-1;
		return 0;
	}
	n=v.size()-1;
	for(int i=0;i<=n;i++){
		for(int j=0;j<3;j++){
			seg[j].up(1,0,n+1,i,1e16,1);
		}
	}
	seg[0].up(1,0,n+1,0,0,1);
	seg[1].up(1,0,n+1,n,0,1);
	for(int i=1;i<=m;i++){
		ll x=seg[0].get(1,0,n+1,g[i][0],g[i][1]+1);
		ll y=seg[1].get(1,0,n+1,g[i][0],g[i][1]+1);
		//cout<<x<<" "<<y<<'\n';
		seg[2].up(1,0,n+1,g[i][2],x+y+g[i][3],0);
		seg[0].up(1,0,n+1,g[i][2],x+g[i][3],0);
		seg[1].up(1,0,n+1,g[i][2],y+g[i][3],0);
	}
	ll ans=seg[2].get(1,0,n+1,0,n+1);
	if(ans==1e16)
		ans=-1;
	cout<<ans;
	return 0;
}

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