oj.uz

Submission #33121

# Submission time Handle Problem Language Result Execution time Memory
33121 2017-10-21T02:44:46 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 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 3 ms 24056 KB Output is correct
6 Correct 3 ms 24056 KB Output is correct
7 Correct 6 ms 24056 KB Output is correct
8 Correct 3 ms 24056 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24056 KB Output is correct
2 Correct 0 ms 24056 KB Output is correct
3 Correct 9 ms 24056 KB Output is correct
4 Correct 0 ms 24056 KB Output is correct
5 Correct 3 ms 24056 KB Output is correct
6 Correct 0 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 9 ms 24056 KB Output is correct
4 Correct 9 ms 24056 KB Output is correct
5 Correct 0 ms 24056 KB Output is correct
6 Correct 0 ms 24056 KB Output is correct
7 Correct 0 ms 24056 KB Output is correct
8 Correct 6 ms 24056 KB Output is correct
9 Correct 3 ms 24056 KB Output is correct
10 Correct 6 ms 24056 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 24216 KB Output is correct
2 Correct 83 ms 24864 KB Output is correct
3 Correct 243 ms 25632 KB Output is correct
4 Correct 303 ms 27168 KB Output is correct
5 Correct 166 ms 25632 KB Output is correct
6 Correct 349 ms 27168 KB Output is correct
7 Correct 419 ms 27168 KB Output is correct
8 Correct 409 ms 27168 KB Output is correct
9 Correct 53 ms 24476 KB Output is correct
10 Correct 143 ms 25632 KB Output is correct
11 Correct 206 ms 27168 KB Output is correct
12 Correct 416 ms 27168 KB Output is correct
13 Correct 359 ms 27168 KB Output is correct
14 Correct 306 ms 27168 KB Output is correct