Submission #714963

#	Time	Username	Problem	Language	Result	Execution time	Memory
714963		dsyz	Pinball (JOI14_pinball)	C++17	51 / 100	916 ms	524288 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node{
	ll s,e,m,val,lazy;
	node *l = nullptr,*r = nullptr;
	node(ll S,ll E){
		s = S;
		e = E;
		m = (s + e) / 2;
		val = 1e18;
		lazy = 1e18;
	}
	void create(){
		if(l == nullptr && s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void propagate(){
		create();
		if(lazy == 1e18) return;
		val = min(val,lazy);
		if(s != e){
			l->lazy = min(l -> lazy,lazy);
			r->lazy = min(r -> lazy,lazy);
		}
	}
	void update(ll S,ll E,ll v){
		if(s == S && e == E) lazy = min(lazy,v);
		else{
			create();
			if(E <= m) l->update(S,E,v);
			else if(S > m) r->update(S,E,v);
			else l->update(S,m,v),r->update(m + 1,E,v);
			l->propagate(),r->propagate();
			val = min(l->val,r->val);
		}
	}
	long long query(ll S,ll E){
		create();
		propagate();
		if(s == S && e == E) return val;
		else if(S > m) return r->query(S,E);
		else if(E <= m) return l->query(S,E);
		else return min(l->query(S,m),r-> query(m + 1,E));
	}
} *root;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll M,N;
	cin>>M>>N;
	root = new node(0,N + 5);
	pair<ll,ll> range[M];
	ll C[M], D[M];
	vector<ll> d;
	for(ll i = 0;i < M;i++){
		cin>>range[i].first>>range[i].second>>C[i]>>D[i];
	}
	ll dp1[M]; //start from column 1
	for(ll i = 0;i < M;i++){
		if(range[i].first == 1) dp1[i] = D[i];
		else dp1[i] = 1e18;
	}
	for(ll i = 0;i < M;i++){
		ll prev = root -> query(range[i].first,range[i].second);
		if(range[i].first == 1){
			dp1[i] = D[i];
		}else{
			if(prev < 1e18) dp1[i] = prev + D[i];
		}
		if(dp1[i] < 1e18) root -> update(C[i],C[i],dp1[i]);
	}
	root = new node(0,N + 5);
	ll dpN[M]; //start from column N
	for(ll i = 0;i < M;i++){
		if(range[i].second == N) dpN[i] = D[i];
		else dpN[i] = 1e18;
	}
	for(ll i = 0;i < M;i++){
		ll prev = root -> query(range[i].first,range[i].second);
		if(range[i].second == N){
			dpN[i] = D[i];
		}else{
			if(prev < 1e18) dpN[i] = prev + D[i];
		}
		if(dpN[i] < 1e18) root -> update(C[i],C[i],dpN[i]);
	}
	ll ans = 2e18 + 5;
	for(ll i = 0;i < M;i++){
		if(dp1[i] < 1e18 && dpN[i] < 1e18){
			ans = min(ans,dp1[i] + dpN[i] - D[i]);
		}
	}
	if(ans >= 1e18) cout<<-1<<'\n';
	else cout<<ans<<'\n';
}

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