Submission #1033149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033149		juicy	Pinball (JOI14_pinball)	C++17	100 / 100	161 ms	23680 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const long long inf = 1e18;

struct Segtree {
	int N;
	vector<long long> S;
	
	Segtree(int N): N(N) {
		S.resize(4 << __lg(N), inf);
	} 

	void upd(int i, long long x, int id, int l, int r) {
		if (l == r) {
			S[id] = min(S[id], x);
			return;
		}
		int md = (l + r) / 2;
		if (i <= md) {
			upd(i, x, id * 2, l, md);
		} else {
			upd(i, x, id * 2 + 1, md + 1, r);
		}
		S[id] = min(S[id * 2], S[id * 2 + 1]);
	}

	void upd(int i, long long x) {
		upd(i, x, 1, 1, N);
	}

	long long qry(int u, int v, int id, int l, int r) {
		if (u <= l && r <= v) {
			return S[id];
		}
		int md = (l + r) / 2;
		if (v <= md) {
			return qry(u, v, id * 2, l, md);
		}
		if (md < u) {
			return qry(u, v, id * 2 + 1, md + 1, r);
		}
		return min(qry(u, v, id * 2, l, md), qry(u, v, id * 2 + 1, md + 1, r));
	}

	long long qry(int u, int v) {
		return qry(u, v, 1, 1, N);
	}
};

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int M, N; cin >> M >> N;
	vector<int> comp = {1, N};
	vector<array<int, 4>> cands;
	for (int i = 0; i < M; ++i) {
		int a, b, c, d; cin >> a >> b >> c >> d;
		cands.push_back({a, b, c, d});
		for (int j = 0; j < 3; ++j) {
			comp.push_back(cands.back()[j]);
		}
	}
	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());
	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < 3; ++j) {
			cands[i][j] = lower_bound(comp.begin(), comp.end(), cands[i][j]) - comp.begin() + 1;
		}
	}
	int K = comp.size();
	Segtree lt(K), rt(K);
	lt.upd(1, 0);
	rt.upd(K, 0);
	long long res = inf;
	for (int i = 0; i < M; ++i) {
		int l = cands[i][0], r = cands[i][1], x = cands[i][2];
		auto a = lt.qry(l, r), b = rt.qry(l, r); 
		if (a != inf && b != inf) {
			res = min(res, a + b + cands[i][3]);
		}
		if (a != inf) {
			lt.upd(x, a + cands[i][3]);
		}
		if (b != inf) {
			rt.upd(x, b + cands[i][3]);
		}
	}
	cout << (res == inf ? -1 : res);
	return 0;
}

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