Submission #405760

#	Time	Username	Problem	Language	Result	Execution time	Memory
405760		ritul_kr_singh	Pinball (JOI14_pinball)	C++17	100 / 100	250 ms	22344 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); }
};

void C(vector<int*> &vals){
	int curr = -1, prev = -INF;
	sort(vals.begin(), vals.end(), [](int* x, int* y){
		return *x < *y;
	});
	for(int i=0; i<(int)vals.size() ;++i){
		if(prev < *vals[i]) ++curr, prev = *vals[i];
		*vals[i] = curr;
	}
}

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

	C(vals);

	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