Submission #793013

#	Time	Username	Problem	Language	Result	Execution time	Memory
793013		bane	Pinball (JOI14_pinball)	C++17	100 / 100	940 ms	339084 KiB

pinball

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

#ifdef LOCAL
#include "algo/debug.h"
#else 
#define debug(...) 42
#endif 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int n, m;

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

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

	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)1e16;
	}

	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,l,r);
		propagate(k,l,r);
		//cout << k << " " << L[k] << " " << R[k] << endl;
		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 0LL;
		if (a > n)return 0LL;
		expand(k,l,r);
		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)1e16;
	for (int i = 0; i < m; i++){
		long long 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);
	//	cout << CostLeft << " " << CostRight << " " << c + 1 << endl;
		long long CoverLeft = CostLeft + d;
		long long CoverRight = CostRight + d;
		if (CoverLeft < (long long)1e16)
			st.range_update(a,c-1,CoverLeft);
		if (CoverRight < (long long)1e16)
			st2.range_update(c+1,b, CoverRight);
		
	}
	cout << (ans == (long long)1e16 ? -1 : ans) << endl;
	return 0;
}

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