Submission #405742

#	Time	Username	Problem	Language	Result	Execution time	Memory
405742		ritul_kr_singh	Pinball (JOI14_pinball)	C++17	100 / 100	314 ms	26316 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int INF = 1e16;

struct SegmentTree{
	vector<int> a; int sz = 1;
	SegmentTree(int n){
		while(sz < n) sz += sz;
		a.assign(2*sz, INF);
	}
	void update(int i, int v, int x, int lx, int rx){
		if(rx-lx==1) return void(a[x] = min(a[x], v));
		int mx = (lx + rx) / 2;
		if(i < mx) update(i, v, 2*x+1, lx, mx);
		else update(i, v, 2*x+2, mx, rx);
		a[x] = min(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int v){ update(i, v, 0, 0, sz); }
	int rangeMin(int l, int r, int x, int lx, int rx){
		if(r<=lx || rx<=l) return INF;
		if(l<=lx && rx<=r) return a[x];
		int mx = (lx + rx) / 2;
		return min(rangeMin(l, r, 2*x+1, lx, mx), rangeMin(l, r, 2*x+2, mx, rx));
	}
	int rangeMin(int l, int r){ return rangeMin(l, r+1, 0, 0, sz); }
};

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int m, n; cin >> m >> n;
	array<int, 4> a[m];
	vector<int> vals = {1, n};
	for(auto &i : a){
		for(int j=0; j<3; ++j) cin >> i[j], vals.push_back(i[j]);
		cin >> i[3];
	}

	sort(vals.begin(), vals.end());
	for(auto &i : a){
		for(int j=0; j<3; ++j) i[j] = lower_bound(vals.begin(), vals.end(), i[j]) - vals.begin();
	}

	int last = lower_bound(vals.begin(), vals.end(), n) - vals.begin();

	SegmentTree dpL(last+1), dpR(last+1);
	dpL.update(0, 0);
	dpR.update(last, 0);

	int res = INF;
	
	for(auto &i : a){
		int l = dpL.rangeMin(i[0], i[1]);
		int r = dpR.rangeMin(i[0], i[1]);
		res = min(res, l + r + i[3]);

		dpL.update(i[2], l + i[3]);
		dpR.update(i[2], r + i[3]);
	}

	cout << (res == INF ? -1 : res);
}

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