Submission #36034

#	Time	Username	Problem	Language	Result	Execution time	Memory
36034		Dat160601	Pinball (JOI14_pinball)	C++14	100 / 100	996 ms	33472 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int m,n;
const int N=1e5+7;
int lef[N],rig[N],md[N];
long long cost[N],costleft[N],costright[N],it[15*N],ans=1e15;
map <int,int> vis;
vector <int> val;
void lw(int x){
	vis[x]++;
	if(vis[x]==1) val.pb(x);
}
void init(int k,int l,int r){
	if(l==r){
		it[k]=1e15;
		return;
	}
	int mid=(l+r)/2;
	init(k*2,l,mid);
	init(k*2+1,mid+1,r);
	it[k]=1e15;
}
void upd(int k,int l,int r,int pos,long long vl){
	if(l>pos || r<pos || l>r) return;
	if(l==r && l==pos){
		it[k]=min(it[k],vl);
		return;
	}
	int mid=(l+r)/2;
	upd(k*2,l,mid,pos,vl);
	upd(k*2+1,mid+1,r,pos,vl);
	it[k]=min(it[k*2],it[k*2+1]);
}
long long get(int k,int l,int r,int L,int R){
	if(l>R || r<L || l>r) return 1e15;
	if(l>=L && r<=R) return it[k];
	int mid=(l+r)/2;
	return min(get(k*2,l,mid,L,R),get(k*2+1,mid+1,r,L,R));
}
int main(){
	ios_base::sync_with_stdio(0);
	cin>>m>>n;
	lw(1);
	lw(n);
	for(int i=1;i<=m;i++){
		cin>>lef[i]>>rig[i]>>md[i]>>cost[i];
		lw(lef[i]);
		lw(rig[i]);
		lw(md[i]);
	}
	sort(val.begin(),val.end());
	int cnt=0;
	for(auto x:val){
		cnt++;
		vis[x]=cnt;
	}
	for(int i=1;i<=m;i++){
		lef[i]=vis[lef[i]];
		rig[i]=vis[rig[i]];
		md[i]=vis[md[i]];
	}
	init(1,1,cnt);
	for(int i=1;i<=m;i++){
		costleft[i]=get(1,1,cnt,lef[i],rig[i]);
		if(lef[i]==1) costleft[i]=0;
		//cout<<costleft[i]<<endl;
		upd(1,1,cnt,md[i],costleft[i]+cost[i]);
	}
	init(1,1,cnt);
	for(int i=1;i<=m;i++){
		costright[i]=get(1,1,cnt,lef[i],rig[i]);
		if(rig[i]==cnt) costright[i]=0;
		ans=min(ans,costleft[i]+costright[i]+cost[i]);
		upd(1,1,cnt,md[i],costright[i]+cost[i]);
	}
	if(ans==1e15) cout<<-1;
	else cout<<ans;
}

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