Submission #29071

#	Time	Username	Problem	Language	Result	Execution time	Memory
29071		PrOAhMeT	Pinball (JOI14_pinball)	C++14	100 / 100	606 ms	79524 KiB

pinball

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXNODE=100000*33;
int n,m,cl[MAXNODE],cr[MAXNODE],tme=1,a,b,c,d,one;
LL f[2][MAXNODE],ans=1e16;

void upd(int &x,int l,int r,int ll,LL val,int d) {

	if(x==0) {
		x=++tme;
		f[0][x]=f[1][x]=1e16;
	}
	if(l==ll&&r==ll) {
		f[d][x]=min(f[d][x],val);
		return;
	}
	int md=(l+r)/2;
	if(ll<=md)
		upd(cl[x],l,md,ll,val,d);
	else upd(cr[x],md+1,r,ll,val,d);
	f[d][x]=min(cl[x]==0?1e17:f[d][cl[x]],cr[x]==0?1e17:f[d][cr[x]]);

}

LL que(int x,int l,int r,int ll,int rr,int d) {

	if(x==0)
		return 1e16;
	if(l>rr||r<ll)
		return 1e16;
	if(l>=ll&&r<=rr)
		return f[d][x];
	int md=(l+r)/2;
	return min(que(cl[x],l,md,ll,rr,d),que(cr[x],md+1,r,ll,rr,d));

}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	f[0][1]=f[1][1]=1e16;
	for(int i=0;i<n;++i) {
		cin>>a>>b>>c>>d;
		LL left=que(1,1,m,a,b,0);
		if(a==1) left=0;
		LL right=que(1,1,m,a,b,1);
		if(b==m) right=0;
		ans=min(ans,left+right+d);
		one=1;
		upd(one,1,m,c,left+d,0);
		one=1;
		upd(one,1,m,c,right+d,1);
	}
	if(ans==1e16)
		cout<<-1<<endl;
	else cout<<ans<<endl;

}

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