Submission #36074

#	Time	Username	Problem	Language	Result	Execution time	Memory
36074		minkank	Pinball (JOI14_pinball)	C++14	100 / 100	326 ms	28744 KiB

pinball

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

const int N = 3e5 + 5;

struct Device {
	int l, r, mid, cost;
};

struct SegmentTree {
	#define mid ((l + r) >> 1)
	long long it[N * 4];
	void init() { for(int i = 0; i < N * 4; ++i) it[i] = 1e18; }
	void update(int node, int l, int r, int p, long long val) {
		if(l > p || r < p) return;
		if(l == r) { it[node] = min(it[node], val); return; }
		update(node << 1, l, mid, p, val); update(node << 1 | 1, mid + 1, r, p, val);
		it[node] = min(it[node << 1], it[node << 1 | 1]);
	}
	long long get(int node, int l, int r, int p, int q) {
		if(l > q || r < p) return 1e18;
		if(p <= l && r <= q) return it[node];
		return min(get(node << 1, l, mid, p, q), get(node << 1 | 1, mid +  1, r, p, q));
	}
	#undef mid
};

int n, m, Start, End;
Device d[N];
vector<int> Value;
SegmentTree Left, Right;
long long ans = 1e18;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	if(n == 1) return cout << 0, 0;
	for(int i = 1; i <= n; ++i) {
		int l, r, mid, cost;
		cin >> l >> r >> mid >> cost;
		d[i] = {l, r, mid, cost};
		Value.push_back(l);
		Value.push_back(r);
		Value.push_back(mid);
	}
	Value.push_back(1); Value.push_back(m);
	sort(Value.begin(), Value.end());
	Value.resize(distance(Value.begin(), unique(Value.begin(), Value.end())));
	for(int i = 1; i <= n; ++i) {
		d[i].l = lower_bound(Value.begin(), Value.end(), d[i].l) - Value.begin();
		d[i].r = lower_bound(Value.begin(), Value.end(), d[i].r) - Value.begin();
		d[i].mid = lower_bound(Value.begin(), Value.end(), d[i].mid) - Value.begin();
	}
	Left.init(); Right.init();
	Left.update(1, 0, Value.size() - 1, 0, 0);
	Right.update(1, 0, Value.size() - 1, Value.size() - 1, 0);
	for(int i = 1; i <= n; ++i) {
		long long valL = Left.get(1, 0, Value.size() - 1, d[i].l, d[i].r),
				  valR = Right.get(1, 0, Value.size() - 1, d[i].l, d[i].r);
		ans = min(ans, valL + valR + d[i].cost);
		Left.update(1, 0, Value.size() - 1, d[i].mid, valL + d[i].cost);
		Right.update(1, 0, Value.size() - 1, d[i].mid, valR + d[i].cost);
	}
	if(ans == 1e18) cout << -1;
	else cout << ans;
}

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