제출 #156539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
156539		Saboon	Pinball (JOI14_pinball)	C++14	100 / 100	463 ms	28300 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 3e5 + 10;
const ll inf = 1e18;

int a[maxn], b[maxn], c[maxn], d[maxn];
vector<int> comp;
ll dp[maxn], pd[maxn];
ll seg[2][4 * maxn];

ll get(int w, int id, int L, int R, int l, int r){
	if (r <= L or R <= l)
		return inf;
	if (l <= L and R <= r)
		return seg[w][id];
	int mid = (L + R) >> 1;
	return min(get(w, 2*id+0, L, mid, l, r), get(w, 2*id+1, mid, R, l, r));
}

void add(int w, int id, int L, int R, int idx, ll val){
	if (idx < L or R <= idx)
		return;
	if (L + 1 == R){
		seg[w][id] = val;
		return;
	}
	int mid = (L + R) >> 1;
	add(w, 2 * id + 0, L, mid, idx, val);
	add(w, 2 * id + 1, mid, R, idx, val);
	seg[w][id] = min(seg[w][2 * id + 0], seg[w][2 * id + 1]);
}

int cmp(int x){
	return lower_bound(comp.begin(), comp.end(), x) - comp.begin();
}

void add(int x){
	comp.push_back(x);
}

int main(){
	ios_base::sync_with_stdio (false);
	cin.tie(0), cout.tie(0);
	int m, n;
	cin >> m >> n;
	for (int i = 1; i <= m; i++){
		cin >> a[i] >> c[i] >> b[i] >> d[i];
		add(a[i]), add(b[i]), add(c[i]);
	}
	comp.push_back(1);
	comp.push_back(n);
	sort(comp.begin(), comp.end());
	comp.resize(unique(comp.begin(), comp.end()) - comp.begin());

	for (int i = 1; i <= m; i++)
		a[i] = cmp(a[i]), b[i] = cmp(b[i]), c[i] = cmp(c[i]);
	n = comp.size();
	for (int i = 0; i < n; i++){
		dp[i] = pd[i] = inf;
		add(0, 1, 0, n, i, inf);
		add(1, 1, 0, n, i, inf);
	}
	dp[0] = pd[n - 1] = 0;
	add(0, 1, 0, n, 0, 0);
	add(1, 1, 0, n, n - 1, 0);
	ll answer = inf;
	for (int i = 1; i <= m; i++){
		ll s = get(0, 1, 0, n, a[i], c[i] + 1);
		ll t = get(1, 1, 0, n, a[i], c[i] + 1);
		answer = min(answer, s + t + d[i]);
		if (s + d[i] < dp[b[i]]){
			dp[b[i]] = s + d[i];
			add(0, 1, 0, n, b[i], dp[b[i]]);
		}
		if (t + d[i] < pd[b[i]]){
			pd[b[i]] = t + d[i];
			add(1, 1, 0, n, b[i], pd[b[i]]);
		}
	}
	if (answer == inf)
		answer = -1;
	cout << answer << endl;
}

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