Submission #197775

#	Time	Username	Problem	Language	Result	Execution time	Memory
197775		Malomalomalomalo	Pinball (JOI14_pinball)	C++14	0 / 100	5 ms	3704 KiB

pinball

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(c) c.begin(), c.end()
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
using namespace std;

typedef long long ll;

const int N = 1e5 + 5;
const ll inf = 1e18;

struct segtree {
	ll t[2*N];
	int n;
	segtree(int n): n(n) {
		for(int i = 1;i < 2*N; ++i)t[i] = inf;
	}
	void edit(int x, ll v){
		x+=n;
		gmin(t[x], v);
		while(x>1){
			x/=2;
			t[x] = min(t[2*x],t[2*x+1]);
		}
	}
	ll query(int l, int r){
		ll res = inf;	
		for(l+=n,r+=n;l < r; l/=2,r/=2){
			if(l&1)gmin(res,t[l++]);	
			if(r&1)gmin(res,t[--r]);	
		}
		return res;
	}
};

struct interval{
	int l,c,r,cst;
};

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int m,n;
	cin >> m >> n;
	map<ll,int> comp;
	comp[1] = 0;
	comp[n] = 0;
	vector<interval> v(m);
	for(int i = 0;i < m; ++i){
		cin >> v[i].l >> v[i].r >> v[i].c >> v[i].cst;	
		comp[v[i].l] = 0;
		comp[v[i].c] = 0;
		comp[v[i].r] = 0;
	}
	int cnt = 0;
	for(auto &a: comp){
		cout << a.first << endl;
		a.second = cnt++;	
	}
	for(int i = 0;i < m; ++i){
		v[i].l = comp[v[i].l];
		v[i].c = comp[v[i].c];
		v[i].r = comp[v[i].r];
	}
	segtree left(cnt), right(cnt);
	left.edit(0,0);
	right.edit(cnt-1,0);
	ll ans = inf;
	for(auto r: v){
		ll bestl = left.query(r.l,r.r+1);
		ll bestr = right.query(r.l,r.r+1);
		gmin(ans, bestl + bestr + r.cst);
		left.edit(r.c,bestl + r.cst);
		right.edit(r.c,bestr + r.cst);
	}
	if(ans == inf)ans = -1;
	cout << ans << '\n';
}

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