Submission #792985

#	Time	Username	Problem	Language	Result	Execution time	Memory
792985		bane	Pinball (JOI14_pinball)	C++17	0 / 100	1 ms	340 KiB

pinball

#include<bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else 
#define debug(...) 42
#endif 

int n, m;

struct Sparse{
	vector<long long>t{(long long)1e18};
	vector<long long>lazy{(long long)1e18};
	vector<int>L{-1},R{-1};

	inline void expand(int k){
		if (L[k] == -1){
			t.push_back((long long)1e18);
			lazy.push_back((long long)1e18);
			L[k] = (int)t.size() - 1;
		}
		if (R[k] == -1){
			t.push_back((long long)1e18);
			R[k] = (int)t.size() - 1;
			lazy.push_back((long long)1e18);
		}
	}

	inline void propagate(int k, int l, int r){
		t[k] = min(t[k], lazy[k]);
		if (l != r){
			lazy[L[k]] = min(lazy[k], lazy[L[k]]);
			lazy[R[k]] = min(lazy[R[k]], lazy[k]);
		}
		lazy[k] = (long long)1e18;
	}

	inline void range_update(int a, int b, long long cost, int l = 1, int r = n, int k = 0){
		if (a > b)return;
		expand(k);
		propagate(k,l,r);
		if (l >= a && r <= b){
			lazy[k] = cost;
			propagate(k,l,r);
			return;
		}
		if (l > b || r < a)return;
		int mid = (l+r) / 2;
		range_update(a,b,cost,l,mid,L[k]);
		range_update(a,b,cost,mid+1,r,R[k]);
	}

	inline long long query(int a, int l = 1, int r = n, int k = 0){
		if (a < 1)return 0;
		if (a > n)return 0;
		expand(k);
		propagate(k,l,r);
		if (l == r){
			return t[k];
		}
		int mid = (l+r) >> 1;
		if (a <= mid)
			return query(a,l,mid,L[k]);
		else
			return query(a,mid+1,r,R[k]);
	}
} st, st2;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> m >> n;
	long long ans = (long long)1e18;
	for (int i = 0; i < m; i++){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		//it ends here
		long long CostLeft = st.query(a-1);	
		long long CostRight = st2.query(b+1);
		ans = min(ans, CostLeft + CostRight + d);
		long long CoverLeft = CostLeft + d;
		long long CoverRight = CostRight + d;
		st.range_update(a,c-1,CoverLeft);
		st2.range_update(c+1,b, CoverRight);
	}
	cout << (ans == (long long)1e18 ? -1 : ans) << endl;
	return 0;
}

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