Submission #282859

#	Time	Username	Problem	Language	Result	Execution time	Memory
282859		oolimry	Pinball (JOI14_pinball)	C++14	51 / 100	959 ms	524292 KiB

pinball

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define L first
#define R second
using namespace std;
typedef long long lint;
typedef pair<int,int> ii;
const lint inf = 1e17;

struct node{
	int s, e, m;
	lint val;
	node *l = nullptr, *r = nullptr;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		val = inf;
		
	}
	
	void create(){
		if(s != e){
			l = new node(s,m);
			r = new node(m+1,e);
		}
	}
	
	void update(int P, lint V){
		val = min(val, V);
		if(s == e) return;
		else if(P <= m){
			if(l == nullptr) create();
			l->update(P,V);
		}
		else{
			if(r == nullptr) create();
			r->update(P,V);
			
		}
	}
	
	lint query(int S, int E){
		if(s == S && E == e) return val;
		else{
			if(l == nullptr) create();
			if(E <= m) return l->query(S,E);
			else if(S >= m+1) return r->query(S,E);
			else return min(l->query(S,m), r->query(m+1,E));
		}
	}
} *Left, *Right;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, len; cin >> n >> len;
	Left = new node(1, len), Right = new node(1, len);
	Left->update(1, 0); Right->update(len, 0);
	
	lint ans = inf;
	
	for(int i = 0;i < n;i++){
		int L, R, M, cost; cin >> L >> R >> M >> cost;
		
		lint fromLeft = Left->query(L, R);
		lint fromRight = Right->query(L, R);
		
		ans = min(ans, fromLeft + fromRight + cost);
				
		Left->update(M, fromLeft + cost);
		Right->update(M, fromRight + cost);
	}
	
	if(ans == inf) ans = -1;
	cout << ans;
}

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