oj.uz

Submission #26552

# Submission time Handle Problem Language Result Execution time Memory
26552 2017-07-02T18:53:57 Z abcdef6199 Pinball (JOI14_pinball) C++
100 / 100
 416 ms 24304 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> II;

const int MAXN = (int) 3e5 + 10;
const LL  INF  = (LL) 1e18;

int n, m, a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int k, x[MAXN];
LL f[MAXN];
LL g[MAXN];

#define mid ((l + r) >> 1)
struct SegTree {
	LL S[MAXN * 5];
	void Build(int k, int l, int r) {
		if (l == r) return S[k] = INF, void(0);
		Build(k << 1 | 0, l, mid);
		Build(k << 1 | 1, mid + 1, r);
		S[k] = INF;
	}
	void Update(int k, int l, int r, int i, LL v) {
		if (l == r) return S[k] = min(S[k], v), void(0);
		if (i <= mid) Update(k << 1, l, mid, i, v);
		else Update(k << 1 | 1, mid + 1, r, i, v);
		S[k] = min(S[k << 1], S[k << 1 | 1]);
	}
	LL Query(int k, int l, int r, int i, int j) {
		if (l > j || r < i) return INF;
		if (i <= l && r <= j) return S[k];
		return min(Query(k << 1, l, mid, i, j), Query(k << 1 | 1, mid + 1, r, i, j));
	} 
} ST;
#undef mid

void Compute(LL f[]) {
	ST.Build(1, 1, k); f[0] = 0;
	for (int i = 0; i <= n; ++i) {
		if (i > 0) {
			int l = lower_bound(x + 1, x + 1 + k, a[i]) - x;
			int r = lower_bound(x + 1, x + 1 + k, b[i]) - x;
			f[i] = ST.Query(1, 1, k, l, r) + d[i];
		}
		ST.Update(1, 1, k, lower_bound(x + 1, x + 1 + k, c[i]) - x, f[i]);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
		x[++k] = a[i];
		x[++k] = b[i];
		x[++k] = c[i];
	}

	x[++k] = 1;
	x[++k] = m;
	sort(x + 1, x + 1 + k);
	k = unique(x + 1, x + 1 + k) - (x + 1);

	a[0] = b[0] = c[0] = 1; d[0] = 0; Compute(f);
	a[0] = b[0] = c[0] = m; d[0] = 0; Compute(g);

	// for (int i = 1; i <= n; ++i) cout << f[i] << " "; cout << endl;
	// for (int i = 1; i <= n; ++i) cout << g[i] << " "; cout << endl;

	LL ans = INF;
	for (int i = 1; i <= n; ++i) ans = min(ans, f[i] + g[i] - d[i]);

	if (ans == INF) ans = -1;
	cout << ans;
	return 0;
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:51:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
pinball.cpp:53:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
                                                ^

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24304 KB Output is correct
2 Correct 66 ms 24304 KB Output is correct
3 Correct 246 ms 24304 KB Output is correct
4 Correct 213 ms 24304 KB Output is correct
5 Correct 163 ms 24304 KB Output is correct
6 Correct 246 ms 24304 KB Output is correct
7 Correct 376 ms 24304 KB Output is correct
8 Correct 343 ms 24304 KB Output is correct
9 Correct 46 ms 24304 KB Output is correct
10 Correct 183 ms 24304 KB Output is correct
11 Correct 253 ms 24304 KB Output is correct
12 Correct 416 ms 24304 KB Output is correct
13 Correct 363 ms 24304 KB Output is correct
14 Correct 313 ms 24304 KB Output is correct