Submission #389844

#	Time	Username	Problem	Language	Result	Execution time	Memory
389844		ogibogi2004	Pinball (JOI14_pinball)	C++14	100 / 100	838 ms	47312 KiB

pinball

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=2e15;
const int MAXM=1e5+6;
const int MAXA=3e5+6;
struct device
{
	ll row,a,b,c,d;
	bool operator<(device const& other)const
	{
		return c<other.c;
	}
};
device d[MAXM];
int n,m;
set<int>xs;
map<int,int>mp;
struct segment_tree
{
	ll tree[4*MAXA];
	void init()
	{
		for(int i=0;i<4*MAXA;i++)tree[i]=INF;
	}
	void update(int l,int r,int idx,int q,ll val)
	{
		if(l>q||r<q)return;
		if(l==r)
		{
			tree[idx]=min(tree[idx],val);
			return;
		}
		int mid=(l+r)/2;
		update(l,mid,idx*2,q,val);
		update(mid+1,r,idx*2+1,q,val);
		tree[idx]=min(tree[idx*2],tree[idx*2+1]);
	}
	ll query(int l,int r,int idx,int ql,int qr)
	{
		if(l>qr||r<ql)return INF;
		if(l>=ql&&r<=qr)return tree[idx];
		int mid=(l+r)/2;
		return min(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
	}
	ll query(ll l,ll r)
	{
		return query(1,MAXA,1,l,r);
	}
	void update(ll q,ll val)
	{
		update(1,MAXA,1,q,val);
	}
}t;
ll dp1[MAXM],dp2[MAXM];
int main()
{
	cin>>m>>n;
	for(int i=2;i<m+2;i++)
	{
		d[i].row=i;
		cin>>d[i].a>>d[i].b>>d[i].c>>d[i].d;
		xs.insert(d[i].a);
		xs.insert(d[i].b);
		xs.insert(d[i].c);
	}
	xs.insert(1);
	xs.insert(n);
	ll ans=INF;
	/*for(int i=2;i<m+2;i++)
	{
		if(d[i].a==1)dp1[i]=d[i].d;
		else
		{
			dp1[i]=INF;
			for(int j=i-1;j>=2;j--)
			{
				if(d[j].c>=d[i].a&&d[j].c<=d[i].b)
				{
					dp1[i]=min(dp1[i],dp1[j]+d[i].d);
				}
			}
		}
	}
	for(int i=2;i<m+2;i++)
	{
		if(d[i].b==n)dp2[i]=d[i].d;
		else
		{
			dp2[i]=INF;
			for(int j=i-1;j>=2;j--)
			{
				if(d[j].c>=d[i].a&&d[j].c<=d[i].b)
				{
					dp2[i]=min(dp2[i],dp2[j]+d[i].d);
				}
			}
		}
		ans=min(ans,dp1[i]+dp2[i]-d[i].d);
	}
	if(ans<INF)cout<<ans<<endl;
	else cout<<"-1\n";*/
	int cnt=0;
	for(auto xd:xs)
	{
		++cnt;
		mp[xd]=cnt;
	}
	n=mp[n];
	for(int i=2;i<m+2;i++)
	{
		d[i].a=mp[d[i].a];
		d[i].b=mp[d[i].b];
		d[i].c=mp[d[i].c];
	}
	t.init();
	for(int i=2;i<m+2;i++)
	{
		if(d[i].a==1)
		{
			dp1[i]=d[i].d;
		}
		else
		{
			dp1[i]=t.query(d[i].a,d[i].b)+d[i].d;
		}
		t.update(d[i].c,dp1[i]);
	}
	t.init();
	for(int i=2;i<m+2;i++)
	{
		if(d[i].b==n)
		{
			dp2[i]=d[i].d;
		}
		else
		{
			dp2[i]=t.query(d[i].a,d[i].b)+d[i].d;
		}
		t.update(d[i].c,dp2[i]);
	}
	for(int i=2;i<m+2;i++)
	{
		ans=min(ans,dp1[i]+dp2[i]-d[i].d);
	}
	if(ans==INF)cout<<"-1\n";
	else cout<<ans<<endl;
return 0;
}

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