oj.uz

Submission #110895

# Submission time Handle Problem Language Result Execution time Memory
110895 2019-05-13T04:22:58 Z rwhendry Pinball (JOI14_pinball) C++14
0 / 100
 3 ms 384 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define INF 1000000000
#define nn 100005
using namespace std;

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

Node* root = NULL;

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

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

Node* update(Node *n, int l, int r, int pos, int target) {
	if(!n) n = new Node();
	if(l == r && l == pos) {
		n->v = min(n->v, target);
		return n;
	}
	
	int 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;
}

int query(Node *n, int l, int r,int kiri, int kanan) {
	if(!n) return 1e9;
	
	if(kiri <= l && r <= kanan) {
		return n->v;
	}
	
	if(kiri > r || kanan < l) return INF;
	
	int 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
	int N, M;
	cin >> N >> M;
	
	for(int 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);
	
	int ans = INF;
	for(int i = 1; i <= N; i++) {
		int queryL = query(rootL, 1, M, a[i], b[i]);
		int 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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -