Submission #380495

#	Time	Username	Problem	Language	Result	Execution time	Memory
380495		pure_mem	Pinball (JOI14_pinball)	C++14	100 / 100	670 ms	172524 KiB

pinball

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e5 + 12, M = 1e9;
const ll INF = 1e18;

struct node{
	node *l, *r;
	ll val = INF;
};
int n, m;

void upd(node *v, int tl, int tr, int pos, ll val){
	if(tl > pos || pos > tr)
		return;
	if(tl == tr){
		v->val = min(v->val, val);
		return;	
	}
	int tm = (tl + tr) / 2;
	if(!v->l)
		v->l = new node();
	if(!v->r)
		v->r = new node();
	upd(v->l, tl, tm, pos, val);
	upd(v->r, tm + 1, tr, pos, val);
	v->val = min(v->l->val, v->r->val);
}
ll get(node *v, int tl, int tr, int l, int r){
	if(tl > r || l > tr || !v)
		return INF;
    if(tl >= l && tr <= r)
    	return v->val;
    int tm = (tl + tr) / 2;
    return min(get(v->l, tl, tm, l, r), get(v->r, tm + 1, tr, l, r));
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> m >> n;
	ll ans = INF;
	node* root1 = new node();
	node* root2 = new node();
	for(int i = 1;i <= m;i++){
		int l, r, c, cost;
		cin >> l >> r >> c >> cost;
		ll cL = get(root1, 1, n, l, r) + cost;
		if(l == 1)
			cL = cost;
		ll cR = get(root2, 1, n, l, r) + cost;
		if(r == n)
			cR = cost;
		ans = min(ans, cL + cR - cost);
		upd(root1, 1, n, c, cL);
		upd(root2, 1, n, c, cR);
	}
	if(ans == INF)
		ans = -1;
	cout << ans;
}

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