제출 #110895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110895		rwhendry	Pinball (JOI14_pinball)	C++14	0 / 100	3 ms	384 KiB

pinball

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