Submission #34402

#	Time	Username	Problem	Language	Result	Execution time	Memory
34402		aome	Pinball (JOI14_pinball)	C++14	100 / 100	396 ms	27168 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
 
const int N = 100005;
const long long INF = 1e18;
 
struct Device {
	int a, b, c, d;
} dv[N];
 
int n, m;
long long f[2][N];
long long it[2][12 * N];
vector<int> zip;
 
void upd(bool t, int i, int l, int r, int p, long long x) {
	if (l == r) {
		it[t][i] = min(it[t][i], x); return;
	}
	int mid = (l + r) >> 1;
	if (mid >= p) upd(t, i << 1, l, mid, p, x);
	else upd(t, i << 1 | 1, mid + 1, r, p, x);
	it[t][i] = min(it[t][i << 1], it[t][i << 1 | 1]);
}
 
long long get(bool t, int i, int l, int r, int u, int v) {
	if (l > v || u > r) return INF;
	if (u <= l && r <= v) return it[t][i];
	int mid = (l + r) >> 1;
	return min(get(t, i << 1, l, mid, u, v), get(t, i << 1 | 1, mid + 1, r, u, v));
}
 
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> dv[i].a >> dv[i].c >> dv[i].b >> dv[i].d;
		zip.push_back(dv[i].a), zip.push_back(dv[i].b), zip.push_back(dv[i].c);
	}
	sort(zip.begin(), zip.end());
	for (int i = 1; i <= n; ++i) {
		dv[i].a = lower_bound(zip.begin(), zip.end(), dv[i].a) - zip.begin() + 1;
		dv[i].b = lower_bound(zip.begin(), zip.end(), dv[i].b) - zip.begin() + 1;
		dv[i].c = lower_bound(zip.begin(), zip.end(), dv[i].c) - zip.begin() + 1;
	}
	for (int i = 0; i < 12 * N; ++i) it[0][i] = it[1][i] = INF;
	int sz = zip.size();
	long long res = INF;
	for (int i = 1; i <= n; ++i) {
		if (zip[dv[i].a - 1] == 1) f[0][i] = 0;
		else f[0][i] = get(0, 1, 1, sz, dv[i].a, dv[i].c);
		if (zip[dv[i].c - 1] == m) f[1][i] = 0;
		else f[1][i] = get(1, 1, 1, sz, dv[i].a, dv[i].c);
		f[0][i] += dv[i].d, f[1][i] += dv[i].d;
		upd(0, 1, 1, sz, dv[i].b, f[0][i]);
		upd(1, 1, 1, sz, dv[i].b, f[1][i]);
		res = min(res, f[0][i] + f[1][i] - dv[i].d);
	}
	cout << ((res == INF) ? -1 : res) << '\n';
}

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