oj.uz

Submission #34581

# Submission time Handle Problem Language Result Execution time Memory
34581 2017-11-13T14:37:00 Z cheater2k Pinball (JOI14_pinball) C++14
67 / 100
 433 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]);
	}
	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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 3 ms 20940 KB Output is correct
5 Correct 3 ms 20940 KB Output is correct
6 Correct 3 ms 20940 KB Output is correct
7 Incorrect 3 ms 20940 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20940 KB Output is correct
2 Correct 0 ms 20940 KB Output is correct
3 Correct 3 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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20940 KB Output is correct
2 Incorrect 6 ms 20940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 21100 KB Output is correct
2 Correct 89 ms 21748 KB Output is correct
3 Correct 279 ms 22516 KB Output is correct
4 Correct 229 ms 24052 KB Output is correct
5 Correct 189 ms 22516 KB Output is correct
6 Correct 286 ms 24052 KB Output is correct
7 Correct 433 ms 24052 KB Output is correct
8 Correct 403 ms 24052 KB Output is correct
9 Correct 53 ms 21360 KB Output is correct
10 Correct 203 ms 22516 KB Output is correct
11 Correct 263 ms 24052 KB Output is correct
12 Correct 429 ms 24052 KB Output is correct
13 Correct 409 ms 24052 KB Output is correct
14 Correct 383 ms 24052 KB Output is correct