Submission #111419

#	Time	Username	Problem	Language	Result	Execution time	Memory
111419		vex	Pinball (JOI14_pinball)	C++14	100 / 100	476 ms	15088 KiB

pinball

/**11:37**/
#include<bits/stdc++.h>
#define maxn 100010
#define INF 100000000000000000
using namespace std;

int m,n;
int a[maxn],b[maxn],c[maxn],d[maxn];
map<int,bool> bio;

int len;
vector<int>poz;
long long dis[4*maxn][2];

void build(int v,int l,int r,int type)
{
	if(l==r)
	{
		if((type==0 && l==0) || (type==1 && l==len-1))dis[v][type]=0;
		else dis[v][type]=INF;
		return;
	}
	
	int mid=(l+r)/2;
	build(2*v,l,mid,type);
	build(2*v+1,mid+1,r,type);
	
	dis[v][type]=min(dis[2*v][type],dis[2*v+1][type]);
}

long long minn(int v,int l,int r,int lt,int rt,int type)
{
	if(l>r || rt<l || lt>r)return INF;
	
	if(lt<=l && r<=rt)return dis[v][type];
	
	int mid=(l+r)/2;
	return min(minn(2*v,l,mid,lt,rt,type),minn(2*v+1,mid+1,r,lt,rt,type));
}

void update(int v,int l,int r,int ind,long long vre,int type)
{
	if(l>r || l>ind || ind>r)return;
	
	if(l==r)
	{
		dis[v][type]=vre;
		return;
	}	
		
	int mid=(l+r)/2;
	update(2*v,l,mid,ind,vre,type);
	update(2*v+1,mid+1,r,ind,vre,type);
	dis[v][type]=min(dis[2*v][type],dis[2*v+1][type]);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin>>m>>n;
	bio[1]=bio[n]=true;
	poz.push_back(1);
	poz.push_back(n);
	for(int i=1;i<=m;i++)
	{
		cin>>a[i]>>b[i]>>c[i]>>d[i];
		if(!bio[c[i]])poz.push_back(c[i]);
		bio[c[i]]=true;
	}
	
	sort(poz.begin(),poz.end());
	len=poz.size();
	//for(int i=0;i<len;i++)cout<<poz[i]<<" ";cout<<endl;
	
	for(int i=1;i<=m;i++)
	{
		a[i]=lower_bound(poz.begin(),poz.end(),a[i])-poz.begin();
		b[i]=upper_bound(poz.begin(),poz.end(),b[i])-poz.begin()-1;
		//cout<<i<<": "<<a[i]<<","<<b[i]<<endl;
	}
	
	long long res=INF;
	for(int type=0;type<2;type++){build(1,0,len-1,type);}
	for(int i=1;i<=m;i++)
	{
		long long cena=minn(1,0,len-1,a[i],b[i],0);
		int pos=lower_bound(poz.begin(),poz.end(),c[i])-poz.begin();
		long long tre=minn(1,0,len-1,pos,pos,0);
		if(cena+d[i]<tre)update(1,0,len-1,pos,cena+d[i],0);
		
		
		long long cena1=minn(1,0,len-1,a[i],b[i],1);
		long long tre1=minn(1,0,len-1,pos,pos,1);
		if(cena1+d[i]<tre1)update(1,0,len-1,pos,cena1+d[i],1);
		
      	if(cena+cena1+d[i]<res)res=cena+cena1+d[i];
      	if(cena+d[i]+tre1<res)res=cena+d[i]+tre1;
      	if(tre+cena1+d[i]<res)res=tre+cena1+d[i];
      	if(tre+tre1<res)res=tre+tre1;
    }
	
	if(res==INF)cout<<"-1"<<endl;
	else cout<<res<<endl;
	return 0;
}

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