Submission #381624

#	Time	Username	Problem	Language	Result	Execution time	Memory
381624		flappybird	Pinball (JOI14_pinball)	C++14	100 / 100	315 ms	36188 KiB

pinball

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
#define MAX 2010100
#define INF ((ll)1<<62)
#define ln '\n'
struct dat {
	ll a, b, c, d;
};
dat arr[MAX];
vector<ll> xpos;
ll s;
ll tree[MAX];
ll lll[MAX], rrr[MAX];
ll l[MAX], r[MAX];
void init(ll x = 1) {
	if (x >= s) {
		tree[x] = INF;
		l[x] = r[x] = x - s + 1;
		return;
	}
	init(x * 2);
	init(x * 2 + 1);
	l[x] = l[x * 2];
	r[x] = r[x * 2 + 1];
	tree[x] = min(tree[x * 2], tree[x * 2 + 1]);
}
void update(ll x, ll a) {
	x += s - 1;
	tree[x] = min(tree[x], a);
	x /= 2;
	while (x) {
		tree[x] = min(tree[x * 2], tree[x * 2 + 1]);
		x /= 2;
	}
}
ll query(ll low, ll high, ll loc = 1) {
	if (l[loc] == low && r[loc] == high) return tree[loc];
	if (high <= r[loc * 2]) return query(low, high, loc * 2);
	if (low >= l[loc * 2 + 1]) return query(low, high, loc * 2 + 1);
	return min(query(low, r[loc * 2], loc * 2), query(l[loc * 2 + 1], high, loc * 2 + 1));
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll M, N;
	cin >> M >> N;
	ll i;
	for (i = 1; i <= M; i++) cin >> arr[i].a >> arr[i].b >> arr[i].c >> arr[i].d;
	xpos.push_back(0), xpos.push_back(N);
	xpos.push_back(1);
	for (i = 1; i <= M; i++) xpos.push_back(arr[i].a), xpos.push_back(arr[i].b), xpos.push_back(arr[i].c);
	sort(xpos.begin(), xpos.end());
	xpos.erase(unique(xpos.begin(), xpos.end()), xpos.end());
	for (i = 1; i <= M; i++) {
		arr[i].a = distance(xpos.begin(), lower_bound(xpos.begin(), xpos.end(), arr[i].a));
		arr[i].b = distance(xpos.begin(), lower_bound(xpos.begin(), xpos.end(), arr[i].b));
		arr[i].c = distance(xpos.begin(), lower_bound(xpos.begin(), xpos.end(), arr[i].c));
	}
	N = xpos.size() - 1;
	s = (ll)1 << (ll)ceil(log2(N));
	init();
	update(1, 0);
	for (i = 1; i <= M; i++) {
		ll res = query(arr[i].a, arr[i].b);
		if (res == INF) lll[i] = INF;
		else lll[i] = res + arr[i].d;
		update(arr[i].c, lll[i]);
	}
	init();
	update(N, 0);
	for (i = 1; i <= M; i++) {
		ll res = query(arr[i].a, arr[i].b);
		if (res == INF) rrr[i] = INF;
		else rrr[i] = res + arr[i].d;
		update(arr[i].c, rrr[i]);
	}
	ll ans = INF;
	for (i = 1; i <= M; i++) ans = min(ans, lll[i] + rrr[i] - arr[i].d);
	if (ans >= INF) cout << -1 << ln;
	else cout << ans << ln;
}

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