Submission #1011650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011650		pcc	Pinball (JOI14_pinball)	C++17	100 / 100	233 ms	46564 KiB

pinball

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second

const int mxn = 6e5+10;
const ll inf = 1e18;


struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
	ll seg[mxn*4];
	SEG(){
		fill(seg,seg+mxn*4,inf);
	}
	void modify(int now,int l,int r,int p,ll v){
		if(l==r){
			seg[now] = min(seg[now],v);
			return;
		}
		if(mid>=p)modify(ls,l,mid,p,v);
		else modify(rs,mid+1,r,p,v);
		seg[now] = min(seg[ls],seg[rs]);
	}
	ll getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else return min(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
	}
#undef ls
#undef rs
#undef mid
};

struct D{
	int s,e,cen,cost;
	D(){}
	D(int ss,int ee,int cc,int co):s(ss),e(ee),cen(cc),cost(co){}
};

SEG lseg,rseg;
ll ans = inf;
ll N,M;
D arr[mxn];
vector<int> all;
ll dist[mxn];

int main(){
	cin>>M>>N;
	all.push_back(N);
	all.push_back(1);
	for(int i = 1;i<=M;i++){
		cin>>arr[i].s>>arr[i].e>>arr[i].cen>>arr[i].cost;
		all.push_back(arr[i].s);
		all.push_back(arr[i].cen);
		all.push_back(arr[i].e);
	}
#define _all(T) T.begin(),T.end()
	sort(_all(all));all.resize(unique(_all(all))-all.begin());
	for(int i = 1;i<=M;i++){
		arr[i].s = lower_bound(_all(all),arr[i].s)-all.begin();
		arr[i].e = lower_bound(_all(all),arr[i].e)-all.begin();
		arr[i].cen = lower_bound(_all(all),arr[i].cen)-all.begin();
	}
	N = all.size()-1;
	lseg.modify(0,0,N,0,0);
	rseg.modify(0,0,N,N,0);
	for(int i = 1;i<=M;i++){
		ll sum = 0;
		ll dist = lseg.getval(0,0,N,arr[i].s,arr[i].e);
		sum += dist;
		lseg.modify(0,0,N,arr[i].cen,dist+arr[i].cost);
		dist = rseg.getval(0,0,N,arr[i].s,arr[i].e);
		sum += dist;
		rseg.modify(0,0,N,arr[i].cen,dist+arr[i].cost);
		ans = min(ans,sum+arr[i].cost);
	}
	cout<<(ans>=inf?-1:ans)<<'\n';
	return 0;
}

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