Submission #26552

#	Time	Username	Problem	Language	Result	Execution time	Memory
26552		abcdef6199	Pinball (JOI14_pinball)	C++98	100 / 100	416 ms	24304 KiB

pinball

#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 (stderr)

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 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49