oj.uz

Submission #34582

# Submission time Handle Problem Language Result Execution time Memory
34582 2017-11-13T14:51:22 Z cheater2k Pinball (JOI14_pinball) C++14
100 / 100
 469 ms 24052 KB 
#include <bits/stdc++.h>
using namespace std;

const long long inf = 1e18;
const int N = 300005;

struct SegmentTree {
	long long T[N << 2];
	void init() {
		for (int i = 1; i < 4 * N; ++i) T[i] = inf;
	}
	
	#define mid ((l + r) >> 1)
	void upd(int v, int l, int r, int pos, long long val) {
		if (l > r || l > pos || r < pos) return;
		if (l == r) { T[v] = min(T[v], val); return; }
		upd(v << 1, l, mid, pos, val); upd(v << 1 | 1, mid + 1, r, pos, val);
		T[v] = min(T[v << 1], T[v << 1 | 1]);
	}

	long long get(int v, int l, int r, int L, int R) {
		if (l > r || R < l || L > r) return inf;
		if (L <= l && r <= R) return T[v];
		return min(get(v << 1, l, mid, L, R), get(v << 1 | 1, mid + 1, r, L, R));
	}
	#undef mid
} seg;

int n, m;
int a[N], b[N], c[N], d[N];
long long f[N][2];

vector<int> z;
void solve(int id) {
	seg.init();
	z.clear();
	for (int i = 1; i <= m; ++i) {
		z.push_back(a[i]);
		z.push_back(b[i]);
		z.push_back(c[i]);
	}
	z.push_back(1);
	sort(z.begin(), z.end()); z.resize(distance(z.begin(), unique(z.begin(), z.end())));

	seg.upd(1, 1, z.size(), 1, 0);
	for (int i = 1; i <= m; ++i) {
		int A = lower_bound(z.begin(), z.end(), a[i]) - z.begin() + 1;
		int B = lower_bound(z.begin(), z.end(), b[i]) - z.begin() + 1;
		int C = lower_bound(z.begin(), z.end(), c[i]) - z.begin() + 1;

		f[i][id] = min(inf, seg.get(1, 1, z.size(), A, B) + d[i]);
		seg.upd(1, 1, z.size(), C, f[i][id]);
	}
}

void rot(int &x) { x = n + 1 - x; }

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> m >> n;
	for (int i = 1; i <= m; ++i) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	solve(0);

	for (int i = 1; i <= m; ++i) {
		rot(a[i]); rot(b[i]); rot(c[i]);
		swap(a[i], b[i]);
	}
	solve(1);

	long long ans = inf;
	for (int i = 1; i <= m; ++i) {
		long long cur = f[i][0] + f[i][1];
		if (cur >= inf) continue;
		ans = min(ans, cur - d[i]);
	}

	if (ans == inf) printf("-1\n"); else printf("%lld\n", ans);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 21100 KB Output is correct
2 Correct 86 ms 21748 KB Output is correct
3 Correct 259 ms 22516 KB Output is correct
4 Correct 216 ms 24052 KB Output is correct
5 Correct 183 ms 22516 KB Output is correct
6 Correct 293 ms 24052 KB Output is correct
7 Correct 419 ms 24052 KB Output is correct
8 Correct 386 ms 24052 KB Output is correct
9 Correct 56 ms 21360 KB Output is correct
10 Correct 166 ms 22516 KB Output is correct
11 Correct 269 ms 24052 KB Output is correct
12 Correct 469 ms 24052 KB Output is correct
13 Correct 409 ms 24052 KB Output is correct
14 Correct 396 ms 24052 KB Output is correct