oj.uz

Submission #110898

# Submission time Handle Problem Language Result Execution time Memory
110898 2019-05-13T04:41:50 Z rwhendry Pinball (JOI14_pinball) C++14
100 / 100
 886 ms 97776 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define INF 1e18
#define nn 100005
using namespace std;

struct Node{
	Node *l, *r;
	long long v;
	Node() : l(NULL), r(NULL), v(INF) {}
};

Node* root = NULL;

long long a[nn], b[nn], c[nn], d[nn];

long long get_value(Node *n) {
	if(!n) return INF;
	return n->v;
}

Node* update(Node *n, long long l, long long r, long long pos, long long target) {
	if(!n) n = new Node();
	if(l == r && l == pos) {
		n->v = min(n->v, target);
		return n;
	}
	
	long long piv = (l + r) >> 1;
	if(pos <= piv) {
		n->l = update(n->l, l, piv, pos, target);
	}
	else {
		n->r = update(n->r, piv+1, r, pos, target);
	}
	
	n->v = min(get_value(n->l), get_value(n->r));
	return n;
}

long long query(Node *n, long long l, long long r,long long kiri, long long kanan) {
	if(!n) return INF;
	
	if(kiri <= l && r <= kanan) {
		return n->v;
	}
	
	if(kiri > r || kanan < l) return INF;
	
	long long piv = (l + r) >> 1;
	
	return min(query(n->l, l, piv, kiri, kanan), query(n->r, piv+1, r, kiri, kanan));
}

int main() {
	// N itu baynak baris, M itu banyak klom
	long long N, M;
	cin >> N >> M;
	
	for(long long i = 1; i <= N; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	
	Node *rootL = NULL, *rootR = NULL;
	rootL = update(rootL, 1, M, 1, 0);
	rootR = update(rootR, 1, M, M, 0);
	
	long long ans = INF;
	for(long long i = 1; i <= N; i++) {
		long long queryL = query(rootL, 1, M, a[i], b[i]);
		long long queryR = query(rootR, 1, M, a[i], b[i]);
		
		ans = min(ans, queryL + queryR + d[i]);
		
		rootL = update(rootL, 1, M, c[i], queryL + d[i]);
		rootR = update(rootR, 1, M, c[i], queryR + d[i]);
	}
	
	if(ans == INF) {
		cout << -1 << "\n";
	}
	else cout << ans << "\n";
}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Correct 4 ms 640 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 4 ms 640 KB Output is correct
17 Correct 7 ms 1280 KB Output is correct
18 Correct 7 ms 512 KB Output is correct
19 Correct 10 ms 1664 KB Output is correct
20 Correct 7 ms 1228 KB Output is correct
21 Correct 4 ms 768 KB Output is correct
22 Correct 7 ms 1536 KB Output is correct
23 Correct 7 ms 1664 KB Output is correct
24 Correct 7 ms 1664 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 4 ms 640 KB Output is correct
17 Correct 7 ms 1280 KB Output is correct
18 Correct 7 ms 512 KB Output is correct
19 Correct 10 ms 1664 KB Output is correct
20 Correct 7 ms 1228 KB Output is correct
21 Correct 4 ms 768 KB Output is correct
22 Correct 7 ms 1536 KB Output is correct
23 Correct 7 ms 1664 KB Output is correct
24 Correct 7 ms 1664 KB Output is correct
25 Correct 41 ms 4684 KB Output is correct
26 Correct 127 ms 17416 KB Output is correct
27 Correct 479 ms 39024 KB Output is correct
28 Correct 387 ms 8208 KB Output is correct
29 Correct 364 ms 38008 KB Output is correct
30 Correct 671 ms 17536 KB Output is correct
31 Correct 743 ms 72620 KB Output is correct
32 Correct 750 ms 60024 KB Output is correct
33 Correct 116 ms 14072 KB Output is correct
34 Correct 427 ms 47736 KB Output is correct
35 Correct 555 ms 97776 KB Output is correct
36 Correct 886 ms 95196 KB Output is correct
37 Correct 667 ms 95288 KB Output is correct
38 Correct 731 ms 95300 KB Output is correct