Submission #111008

#	Time	Username	Problem	Language	Result	Execution time	Memory
111008		Pajaraja	Pinball (JOI14_pinball)	C++17	100 / 100	818 ms	37368 KiB

pinball

#include <bits/stdc++.h>
#define MAXN 100007
#define LINF 1000000000000000000LL
using namespace std;
long long dpl[MAXN],dpr[MAXN],seg[2][12*MAXN],d[MAXN];
int a[MAXN],b[MAXN],c[MAXN],sz;
vector<int> v;
map<int,int> mp;
void upd(int k,int l,int r,int v,long long a,int ind)
{
	if(l==r) {seg[k][ind]=min(seg[k][ind],a); return;}
	int s=(l+r)/2;
	if(v<=s) upd(k,l,s,v,a,2*ind);
	else upd(k,s+1,r,v,a,2*ind+1);
	seg[k][ind]=min(seg[k][2*ind],seg[k][2*ind+1]);
}
long long val(int k,int l,int r,int lt,int rt,int ind)
{
	if(l>=lt && r<=rt) return seg[k][ind];
	if(rt<l || lt>r) return LINF;
	int s=(l+r)/2;
	return min(val(k,l,s,lt,rt,2*ind),val(k,s+1,r,lt,rt,2*ind+1));
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	int n,m; cin>>m>>n;
	v.push_back(1);
	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(n);
	sort(v.begin(),v.end());
	sz=v.size();
	for(int i=0;i<sz;i++) mp[v[i]]=i;
	fill(seg[1],seg[1]+12*MAXN,LINF); fill(seg[0],seg[0]+12*MAXN,LINF);
	upd(0,0,sz,mp[1],0,1); upd(1,0,sz,mp[n],0,1);
	long long sol=LINF;
	for(int i=0;i<m;i++)
	{
		long long x=val(0,0,sz,mp[a[i]],mp[b[i]],1),y=val(1,0,sz,mp[a[i]],mp[b[i]],1);
		//cout<<mp[a[i]]<<" "<<y<<endl;
		upd(0,0,sz,mp[c[i]],x+d[i],1); upd(1,0,sz,mp[c[i]],y+d[i],1);
		sol=min(sol,x+y+d[i]);
	}
	if(sol==LINF) sol=-1;
	cout<<sol;
}

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