Submission #282860

#	Time	Username	Problem	Language	Result	Execution time	Memory
282860		oolimry	Pinball (JOI14_pinball)	C++14	100 / 100	237 ms	16648 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 segment{
	lint tree[600005];
	int n;
	segment(int N){
		n = N;
		fill(tree, tree+2*n, inf);
	}
	void update(int i, lint v){
		for(i += n;i > 0;i >>= 1) tree[i] = min(tree[i], v);
	}
	lint query(int l, int r){
		lint res = inf;
		for(l += n, r += n+1;l < r;l >>= 1, r >>= 1){
			if(l&1) res = min(res, tree[l++]);
			if(r&1) res = min(res, tree[--r]);
		}
		return res;
	}
} *Left, *Right;

int A[100005], B[100005], C[100005], D[100005];
vector<int> dis;
int get(lint x){
	return lower_bound(all(dis), x) - dis.begin();
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, len; cin >> n >> len;
	
	lint ans = inf;
	for(int i = 0;i < n;i++){
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		dis.push_back(A[i]);
		dis.push_back(B[i]);
		dis.push_back(C[i]);
	}
	dis.push_back(1);
	dis.push_back(len);
	
	sort(all(dis));
	dis.erase(unique(all(dis)), dis.end());
	
	Left = new segment(sz(dis)), Right = new segment(sz(dis));
	Left->update(get(0), 0); Right->update(get(len), 0);
	
	for(int i = 0;i < n;i++){
		int L = get(A[i]), R = get(B[i]), M = get(C[i]), cost = D[i];
				
		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: 49 / 49