oj.uz

Submission #34401

# Submission time Handle Problem Language Result Execution time Memory
34401 2017-11-11T02:56:47 Z aome Pinball (JOI14_pinball) C++14
100 / 100
 419 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;
 
	bool operator < (const Device& to) const {
		return c < to.c;
	}
} 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 3 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 6 ms 24056 KB Output is correct
7 Correct 0 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 3 ms 24056 KB Output is correct
2 Correct 3 ms 24056 KB Output is correct
3 Correct 6 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 6 ms 24056 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24056 KB Output is correct
2 Correct 0 ms 24056 KB Output is correct
3 Correct 6 ms 24056 KB Output is correct
4 Correct 3 ms 24056 KB Output is correct
5 Correct 13 ms 24056 KB Output is correct
6 Correct 9 ms 24056 KB Output is correct
7 Correct 0 ms 24056 KB Output is correct
8 Correct 0 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 66 ms 24864 KB Output is correct
3 Correct 253 ms 25632 KB Output is correct
4 Correct 286 ms 27168 KB Output is correct
5 Correct 179 ms 25632 KB Output is correct
6 Correct 393 ms 27168 KB Output is correct
7 Correct 403 ms 27168 KB Output is correct
8 Correct 399 ms 27168 KB Output is correct
9 Correct 43 ms 24476 KB Output is correct
10 Correct 163 ms 25632 KB Output is correct
11 Correct 213 ms 27168 KB Output is correct
12 Correct 419 ms 27168 KB Output is correct
13 Correct 359 ms 27168 KB Output is correct
14 Correct 336 ms 27168 KB Output is correct