제출 #645999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645999		ymm	Pinball (JOI14_pinball)	C++17	100 / 100	200 ms	23492 KiB

pinball

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
const int M = 300'010;
const ll inf = 1e15;
int n, m;
int a[N], b[N], c[N];
ll d[N];

struct seg {
	ll t[2*M];
	ll get(int l, int r)
	{
		l += M; r += M;
		ll ans = inf;
		while (l < r) {
			if (l&1) ans = min(ans, t[l++]);
			if (r&1) ans = min(ans, t[--r]);
			l /= 2; r /= 2;
		}
		return ans;
	}
	void up(int i, ll x)
	{
		i += M;
		while (i) {
			t[i] = min(t[i], x);
			i /= 2;
		}
	}
} dpr, dpl;

vector<pair<int,int*>> cmp_vec;

int compress()
{
	vector<int> vec;
	for (auto [x, _] : cmp_vec)
		vec.push_back(x);
	sort(vec.begin(), vec.end());
	vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
	for (auto [x, p] : cmp_vec) {
		if (p) {
			*p =   lower_bound(vec.begin(), vec.end(), x)
			     - vec.begin();
		}
	}
	return vec.size();
}

void init_dp()
{
	fill(dpr.t, dpr.t + 2*M, inf);
	fill(dpl.t, dpl.t + 2*M, inf);
	dpr.up(m-1, 0);
	dpl.up(0, 0);
}

ll calc_ans()
{
	init_dp();
	ll ans = inf;
	Loop (dev,0,n) {
		ans = min(  dpl.get(a[dev], b[dev]+1)
		          + dpr.get(a[dev], b[dev]+1)
			  + d[dev],
		          ans);
		ll mnr = dpr.get(c[dev], b[dev]+1);
		ll mnl = dpl.get(a[dev], c[dev]+1);
		dpr.up(c[dev], mnr + d[dev]);
		dpl.up(c[dev], mnl + d[dev]);
	}
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (i,0,n) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		cmp_vec.push_back({a[i], &a[i]});
		cmp_vec.push_back({b[i], &b[i]});
		cmp_vec.push_back({c[i], &c[i]});
	}
	cmp_vec.push_back({1, NULL});
	cmp_vec.push_back({m, NULL});
	m = compress();
	ll ans = calc_ans();
	cout << (ans == inf? -1: ans)  << '\n';
}

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