Submission #88128

#	Time	Username	Problem	Language	Result	Execution time	Memory
88128		KCSC	Pinball (JOI14_pinball)	C++14	100 / 100	417 ms	31772 KiB

pinball

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

const int DIM = 300005;

struct Segment {
	int lef, rig, pos, val; } seg[DIM];
pair<long long, long long> sgt[DIM << 2]; vector<int> lst;

void update(int tp, int nd, int le, int ri, int ps, long long vl) {
	if (le == ri) {
		!tp ? (sgt[nd].first = min(sgt[nd].first, vl)) :
			  (sgt[nd].second = min(sgt[nd].second, vl)); }
	else {
		int md = (le + ri) / 2;
		(ps <= md) ? update(tp, nd << 1, le, md, ps, vl) :
					 update(tp, nd << 1 | 1, md + 1, ri, ps, vl);
		sgt[nd] = make_pair(min(sgt[nd << 1].first, sgt[nd << 1 | 1].first),
							min(sgt[nd << 1].second, sgt[nd << 1 | 1].second)); } }

pair<long long, long long> query(int nd, int le, int ri, int st, int en) {
	if (st <= le and ri <= en) {
		return sgt[nd]; }
	else {
		int md = (le + ri) / 2;
		if (en <= md) {
			return query(nd << 1, le, md, st, en); }
		if (md <  st) {	
			return query(nd << 1 | 1, md + 1, ri, st, en); }
		auto lans = query(nd << 1, le, md, st, en), 
			 rans = query(nd << 1 | 1, md + 1, ri, st, en);
		return make_pair(min(lans.first, rans.first), 
						 min(lans.second, rans.second)); } }

inline int f(const int x) {
	return lower_bound(lst.begin(), lst.end(), x) - lst.begin() + 1; }

int main(void) {
#ifdef HOME
	freopen("pinball.in", "r", stdin);
	freopen("pinball.out", "w", stdout);
#endif
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		int l, r, p, d; cin >> l >> r >> p >> d; seg[i] = {l, r, p, d};
		lst.push_back(l); lst.push_back(r); lst.push_back(p); }
	lst.push_back(1); lst.push_back(m); sort(lst.begin(), lst.end());
	lst.resize(unique(lst.begin(), lst.end()) - lst.begin());
	int k = (int) lst.size();
	for (int i = 1; i <= (k << 2); ++i) {
		sgt[i].first = sgt[i].second = (1LL << 60); }
	update(0, 1, 1, k, 1, 0); update(1, 1, 1, k, k, 0);
	long long ans = (1LL << 60);
	for (int i = 1; i <= n; ++i) {
		int l = f(seg[i].lef), r = f(seg[i].rig), p = f(seg[i].pos), d = seg[i].val;
		pair<long long, long long> pr = query(1, 1, k, l, r);
		ans = min(ans, pr.first + pr.second + d);
		update(0, 1, 1, k, p, pr.first + d); update(1, 1, 1, k, p, pr.second + d); }
	cout << (ans <= 1000000000000000LL ? ans : -1) << endl;
	return 0; }

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