Submission #239802

#	Time	Username	Problem	Language	Result	Execution time	Memory
239802		MvC	Pinball (JOI14_pinball)	C++11	100 / 100	261 ms	14840 KiB

pinball

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=1e5+50;
const ll mod=1e9+7;
using namespace std;
int m,n,a[nmax],b[nmax],c[nmax],d[nmax],sz,i;
ll f[nmax],g[nmax],x,st[12*nmax],rs;
vector<int>vc;
void upd(int nod,int l,int r,int p,ll v)
{
	if(l==r)
	{
		st[nod]=min(st[nod],v);
		return;
	}
	int mid=(l+r)/2;
	if(p<=mid)upd(2*nod,l,mid,p,v);
	else upd(2*nod+1,mid+1,r,p,v);
	st[nod]=min(st[2*nod],st[2*nod+1]);
}
ll qry(int nod,int l,int r,int tl,int tr)
{
	if(tr<l || tl>r)return llinf;
	if(tl<=l && r<=tr)return st[nod];
	int mid=(l+r)/2;
	return min(qry(2*nod,l,mid,tl,tr),qry(2*nod+1,mid+1,r,tl,tr));
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>m>>n;
	for(i=1;i<=m;i++)
	{
		cin>>a[i]>>b[i]>>c[i]>>d[i];
		vc.pb(a[i]);
		vc.pb(b[i]);
		vc.pb(c[i]);
	}
	vc.pb(1),vc.pb(n);
	sort(all(vc));
	vc.resize(unique(all(vc))-vc.begin());
	sz=lun(vc);
	for(i=1;i<=m;i++)
	{
		a[i]=lower_bound(all(vc),a[i])-vc.begin()+1;
		b[i]=lower_bound(all(vc),b[i])-vc.begin()+1;
		c[i]=lower_bound(all(vc),c[i])-vc.begin()+1;
	}
	for(i=1;i<=4*sz;i++)st[i]=llinf;
	for(i=1;i<=m;i++)
	{
		f[i]=llinf;
		x=qry(1,1,sz,a[i],b[i]);
		if(a[i]==1)f[i]=d[i];
		else if(x!=llinf)f[i]=x+d[i];
		upd(1,1,sz,c[i],f[i]);
	}
	for(i=1;i<=4*sz;i++)st[i]=llinf;
	rs=llinf;
	for(i=1;i<=m;i++)
	{
		g[i]=llinf;
		x=qry(1,1,sz,a[i],b[i]);
		if(b[i]==sz)g[i]=d[i];
		else if(x!=llinf)g[i]=x+d[i];
		upd(1,1,sz,c[i],g[i]);
		if(f[i]!=llinf && g[i]!=llinf)rs=min(rs,f[i]+g[i]-d[i]);
	}
	if(rs==llinf)rs=-1;
	cout<<rs<<endl;
	return 0;
}

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