제출 #553788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
553788		QwertyPi	Pinball (JOI14_pinball)	C++14	0 / 100	1 ms	340 KiB

pinball

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int M = 3e5+3;
int m, n;
const ll inf = 1LL << 60;
ll dp1[M], dp2[M], a[M], b[M], c[M], d[M];

struct SegTree{
	ll t[M * 4], tag[M * 4];
	void pushdown(int u, int v){
		if(tag[u] != -1){
			t[v] = tag[v] = tag[u];
		}
	}
	void push(int v){
		if(tag[v] != -1){
			pushdown(v, v * 2);
			pushdown(v, v * 2 + 1);
		}
		tag[v] = -1;
	}
	void build(ll* val, int v = 1, int tl = 0, int tr = n - 1){
		if(tl == tr){
			t[v] = val[tl]; tag[v] = -1;
			return;
		}
		int tm = (tl + tr) / 2;
		build(val, v * 2, tl, tm);
		build(val, v * 2 + 1, tm + 1, tr);
		t[v] = min(t[v * 2], t[v * 2 + 1]);
		tag[v] = -1;
	}
	
	ll qry_min(int l, int r, int v = 1, int tl = 0, int tr = n - 1){
		if(l > r) return inf;
		if(l <= tl && tr <= r) return t[v];
		push(v);
		int tm = (tl + tr) / 2;
		return min(qry_min(l, min(tm, r), v * 2, tl, tm), 
				   qry_min(max(tm + 1, l), r, v * 2 + 1, tm + 1, tr));
	}
	void upd(int l, int r, ll val, int v = 1, int tl = 0, int tr = n - 1){
		if(l > r) return;
		if(l <= tl && tr <= r){
			t[v] = tag[v] = val;
			return;
		}
		push(v);
		int tm = (tl + tr) / 2;
		upd(l, min(tm, r), val, v * 2, tl, tm);
		upd(max(tm + 1, l), r, val, v * 2 + 1, tm + 1, tr);
		t[v] = min(t[v * 2], t[v * 2 + 1]);
	}
} seg1, seg2;

int main(){
	cin >> m >> n;
	for(int i = 0; i < m; i++){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	{
		set<int> S; for(int i = 0; i < m; i++) S.insert(a[i]), S.insert(b[i]), S.insert(c[i]);
		map<int, int> M; int idx = 0; for(auto i : S) M[i] = idx++; n = idx;
		for(int i = 0; i < m; i++) a[i] = M[a[i]], b[i] = M[b[i]], c[i] = M[c[i]];
	}
//	cout << n << endl;
//	for(int i = 0; i < m; i++){
//		cout << a[i] << ' ' << b[i] << ' ' << c[i] << endl;
//	}
	fill(dp1 + 1, dp1 + n, inf);
	fill(dp2, dp2 + n - 1, inf);
	seg1.build(dp1);
	seg2.build(dp2);
	ll ans = inf;
	for(int i = 0; i < m; i++){
		ans = min(ans, seg1.qry_min(a[i], n - 1) + seg2.qry_min(0, b[i]) + d[i]);
		{
			ll mn = seg1.qry_min(a[i], c[i]);
			seg1.upd(c[i], c[i], min(seg1.qry_min(c[i], c[i]), mn + d[i]));
		}
		{
			ll mn = seg2.qry_min(c[i], b[i]);
			seg2.upd(c[i], c[i], min(seg2.qry_min(c[i], c[i]), mn + d[i]));
		}
//		for(int i = 0; i < n; i++){
//			cout << seg1.qry_min(i, i) << ' ';
//		}
//		cout << endl;
//		for(int i = 0; i < n; i++){
//			cout << seg2.qry_min(i, i) << ' ';
//		}
//		cout << endl;
	}
	cout << (ans == inf ? -1 : ans) << endl;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 49