Submission #290213

#	Time	Username	Problem	Language	Result	Execution time	Memory
290213		shivensinha4	Pinball (JOI14_pinball)	C++17	100 / 100	302 ms	36184 KiB

pinball

#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
 
ll INF = 1e15;
 
class SegmentTree {
	private:
		vector<ll> tree; int n;
		ll bound = INF;
		
		ll merge(ll a, ll b) {
			return min(a, b);
		}
		
		void update(int i, ll val, int l, int r, int p) {
			if (l > i or r < i) return;
			if (l == r) {
				tree[p] = min(tree[p], val);
				return;
			}
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			update(i, val, l, mid, c1); update(i, val, mid+1, r, c2);
			tree[p] = merge(tree[c1], tree[c2]);
		}
		
		ll mn(int i, int j, int l, int r, int p) {
			if (l > j or r < i) return bound;
			if (l >= i and r <= j) return tree[p];
			
			int mid = (l + r) / 2;
			int c1 = 2*p+1, c2 = 2*p+2;
			return merge(mn(i, j, l, mid, c1), mn(i, j, mid+1, r, c2));
		}
	
	public: 
		SegmentTree(int N) {
			n = N;
			tree.resize(4*n, INF);
		}
		
		ll mn(int i, int j) {
			return mn(i, j, 0, n-1, 0);
		}
		
		void update(int i, ll val) {
			update(i, val, 0, n-1, 0);
		}
};
 
 
 
int main() {
	#ifndef ONLINE_JUDGE
	//freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int m, n; cin >> m >> n;
	vector<ll> cost(m); vi l(m), r(m), c(m);
	vi allPts;
	allPts.push_back(1); allPts.push_back(n);
	for_(i, 0, m) {
		cin >> l[i] >> r[i] >> c[i] >> cost[i];
		allPts.push_back(l[i]); allPts.push_back(r[i]); allPts.push_back(c[i]);
	}
	
	sort(allPts.begin(), allPts.end());
	gp_hash_table<int, int> id;
	int pt = 0;
	for_(i, 0, allPts.size()) if (i == 0 or allPts[i] != allPts[i-1]) id[allPts[i]] = pt++;
	
	for_(i, 0, m) {
		l[i] = id[l[i]]; r[i] = id[r[i]]; c[i] = id[c[i]];
	}
	
	int pointCount = id[allPts.back()]+1;
	SegmentTree rCost(pointCount), lCost(pointCount);
	
	ll ans = INF;
	for_(i, 0, m) {
		ll lc = lCost.mn(l[i], r[i]), rc = rCost.mn(l[i], r[i]);
		if (r[i] == pointCount-1) rc = 0;
		if (l[i] == 0) lc = 0;
		if (lc != INF) lCost.update(c[i], lc+cost[i]);
		if (rc != INF) rCost.update(c[i], rc+cost[i]);
		ans = min(ans, lc+rc+cost[i]);
	}
	
	cout << (ans == INF ? -1 : ans) << endl;
	
	return 0;
}

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