제출 #110896

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

pinball

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