oj.uz

Submission #18569

# Submission time Handle Problem Language Result Execution time Memory
18569 2016-02-09T10:06:57 Z choyi0521 Pinball (JOI14_pinball) C++14
100 / 100
 884 ms 299000 KB 
#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.0 / 11.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1340 KB Output is correct
3 Correct 0 ms 1472 KB Output is correct
4 Correct 2 ms 2132 KB Output is correct
5 Correct 0 ms 2132 KB Output is correct
6 Correct 0 ms 2264 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1736 KB Output is correct
3 Correct 4 ms 2924 KB Output is correct
4 Correct 3 ms 1208 KB Output is correct
5 Correct 7 ms 5300 KB Output is correct
6 Correct 3 ms 2264 KB Output is correct
7 Correct 3 ms 2264 KB Output is correct
8 Correct 4 ms 5300 KB Output is correct
9 Correct 11 ms 5828 KB Output is correct
10 Correct 11 ms 5960 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 8468 KB Output is correct
2 Correct 166 ms 41732 KB Output is correct
3 Correct 443 ms 70244 KB Output is correct
4 Correct 339 ms 2396 KB Output is correct
5 Correct 364 ms 84104 KB Output is correct
6 Correct 569 ms 15728 KB Output is correct
7 Correct 793 ms 151160 KB Output is correct
8 Correct 724 ms 101924 KB Output is correct
9 Correct 92 ms 35924 KB Output is correct
10 Correct 399 ms 148124 KB Output is correct
11 Correct 569 ms 292268 KB Output is correct
12 Correct 884 ms 299000 KB Output is correct
13 Correct 799 ms 296756 KB Output is correct
14 Correct 728 ms 295832 KB Output is correct