Submission #752638

#	Time	Username	Problem	Language	Result	Execution time	Memory
752638		jmyszka2007	Pinball (JOI14_pinball)	C++17	100 / 100	533 ms	29648 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;
constexpr int LIM = 1e5;
constexpr int base = (1 << 19);
int lft[LIM + 10];
int rgt[LIM + 10];
int mid[LIM + 10];
int cost[LIM + 10];
ll dp[LIM + 10][2];
ll tri[2 * base];
map<int, int>con;
void reset() {
	for(int i = 0; i < 2 * base; i++) {
		tri[i] = 1e18;
	}
}
void upd(int v, ll x) {
	v += base;
	while(v > 0) {
		tri[v] = min(tri[v], x);
		v /= 2;
	}
}
ll que(int l, int r) {
	l += base;
	r += base;
	ll ans = 1e18;
	while(l <= r) {
		if(l & 1) {
			ans = min(ans, tri[l]);
		}
		if(!(r & 1)) {
			ans = min(ans, tri[r]);
		}
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
	return ans;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> lft[i] >> rgt[i] >> mid[i] >> cost[i];
		con[lft[i]] = 0;
		con[rgt[i]] = 0;
		con[mid[i]] = 0;
	}
	con[1] = 0;
	con[m] = 0;
	int k = 1;
	for(auto x : con) {
		con[x.st] = k++;
	}
	reset();
	upd(1, 0);
	for(int i = 1; i <= n; i++) {
		dp[i][0] = que(con[lft[i]], con[rgt[i]]) + cost[i];
		upd(con[mid[i]], dp[i][0]);
	}
	reset();
	upd(con.size(), 0);
	for(int i = 1; i <= n; i++) {
		dp[i][1] = que(con[lft[i]], con[rgt[i]]) + cost[i];
		upd(con[mid[i]], dp[i][1]);
	}
	ll ans = 1e18;
	for(int i = 1; i <= n; i++) {
		//cout << dp[i][0] << ' ' << dp[i][1] << '\n';
		ans = min(ans, dp[i][0] + dp[i][1] - cost[i]);
	}
	if(ans == 1e18) {
		cout << -1 << '\n';
	}
	else {
		cout << ans << '\n';
	}
}

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