oj.uz

Submission #34402

# Submission time Handle Problem Language Result Execution time Memory
34402 2017-11-11T02:57:12 Z aome Pinball (JOI14_pinball) C++14
100 / 100
 396 ms 27168 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24056 KB Output is correct
2 Correct 6 ms 24056 KB Output is correct
3 Correct 3 ms 24056 KB Output is correct
4 Correct 3 ms 24056 KB Output is correct
5 Correct 3 ms 24056 KB Output is correct
6 Correct 0 ms 24056 KB Output is correct
7 Correct 6 ms 24056 KB Output is correct
8 Correct 0 ms 24056 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24056 KB Output is correct
2 Correct 0 ms 24056 KB Output is correct
3 Correct 3 ms 24056 KB Output is correct
4 Correct 3 ms 24056 KB Output is correct
5 Correct 0 ms 24056 KB Output is correct
6 Correct 6 ms 24056 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24056 KB Output is correct
2 Correct 0 ms 24056 KB Output is correct
3 Correct 0 ms 24056 KB Output is correct
4 Correct 3 ms 24056 KB Output is correct
5 Correct 0 ms 24056 KB Output is correct
6 Correct 6 ms 24056 KB Output is correct
7 Correct 3 ms 24056 KB Output is correct
8 Correct 6 ms 24056 KB Output is correct
9 Correct 6 ms 24056 KB Output is correct
10 Correct 0 ms 24056 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24216 KB Output is correct
2 Correct 73 ms 24864 KB Output is correct
3 Correct 249 ms 25632 KB Output is correct
4 Correct 293 ms 27168 KB Output is correct
5 Correct 153 ms 25632 KB Output is correct
6 Correct 359 ms 27168 KB Output is correct
7 Correct 396 ms 27168 KB Output is correct
8 Correct 353 ms 27168 KB Output is correct
9 Correct 36 ms 24476 KB Output is correct
10 Correct 159 ms 25632 KB Output is correct
11 Correct 239 ms 27168 KB Output is correct
12 Correct 383 ms 27168 KB Output is correct
13 Correct 339 ms 27168 KB Output is correct
14 Correct 329 ms 27168 KB Output is correct