Submission #18569

#	Time	Username	Problem	Language	Result	Execution time	Memory
18569		choyi0521	Pinball (JOI14_pinball)	C++14	100 / 100	884 ms	299000 KiB

pinball

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int n, m;
struct st {
	ll mini[2] = { (ll)1e18,(ll)1e18 };
	st *left=NULL, *right=NULL;
}tree;
void update(st *h, int l, int r, int g,ll x, int type) {
	if (r < g || g < l) return;
	h->mini[type] = min(h->mini[type], x);
	if (l != r) {
		if (!h->left) h->left = new st;
		if (!h->right) h->right = new st;
		update(h->left, l, (l + r) / 2, g, x, type);
		update(h->right, (l + r) / 2+1,r, g, x, type);
	}
}
ll query(st *h, int l, int r, int gl, int gr, int type) {
	if (r < gl || gr < l) return 1e18;
	if (gl <= l && r <= gr) return h->mini[type];
	if (!h->left) h->left = new st;
	if (!h->right) h->right = new st;
	return min(query(h->left, l, (l + r) / 2, gl, gr, type),
		query(h->right, (l + r) / 2 + 1, r, gl, gr, type));
}
int main() {
	scanf("%d %d", &m, &n);
	st *rt = new st;
	update(rt, 1, n, 1, 0, 0);
	update(rt, 1, n, n, 0, 1);
	ll res = 1e18;
	for (int i = 0; i < m; i++) {
		int a, b, c, d;
		scanf("%d %d %d %d", &a, &b, &c, &d);
		ll ql = query(rt, 1, n, a, b, 0), qr = query(rt, 1, n, a, b, 1);
		res = min(res, ql+qr+d);
		update(rt, 1, n, c, ql+d, 0);
		update(rt, 1, n, c, qr+d, 1);
	}
	printf("%lld", res==1e18?-1:res);
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49