Submission #1270072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270072		altern23	Pinball (JOI14_pinball)	C++20	100 / 100	168 ms	24756 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 1e5;
const ll INF = 4e18;
const int MOD = 998244353;

ll L[MAXN + 5], R[MAXN + 5], C[MAXN + 5], W[MAXN + 5];

struct ST{
	ll N;
	vector<ll> sg;
	ST(ll _n){
		N = _n;
		sg.resize(4 * N + 5, INF);
	}
	
	void upd(ll l, ll r, ll cur, ll idx, ll val){
		if(l == r){
			sg[cur] = min(sg[cur], val);
		}
		else{
			ll mid = (l + r) / 2;
			if(idx <= mid) upd(l, mid, cur * 2, idx, val);
			else upd(mid + 1, r, cur * 2 + 1, idx, val);
			sg[cur] = min(sg[cur * 2], sg[cur * 2 + 1]);
		}
	}
	
	ll query(ll l, ll r, ll cur, ll x, ll y){
		if(l > y || r < x) return INF;
		if(l >= x && r <= y) return sg[cur];
		ll mid = (l + r) / 2;
		return min(query(l, mid, cur * 2, x, y), query(mid + 1, r, cur * 2 + 1, x, y));
	}
};

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tc = 1;
	// cin >> tc;
	for(;tc--;){
		ll M, N; cin >> M >> N;
		vector<ll> comp;
		comp.push_back(1), comp.push_back(N);
		for(int i = 1; i <= M; i++){
			cin >> L[i] >> R[i] >> C[i] >> W[i];
			comp.push_back(L[i]), comp.push_back(C[i]), comp.push_back(R[i]);
		}
		
		sort(comp.begin(), comp.end());
		
		comp.erase(unique(comp.begin(), comp.end()), comp.end());
		
		auto get_id = [&](ll idx){
			return lower_bound(comp.begin(), comp.end(), idx) - comp.begin() + 1;
		};
		
		ll K = comp.size();
		
		ST ps(K), sf(K);
		
		ps.upd(1, K, 1, get_id(1), 0);
		sf.upd(1, K, 1, get_id(N), 0);
		
		ll ans = INF;
		for(int i = 1; i <= M; i++){
			L[i] = get_id(L[i]), C[i] = get_id(C[i]), R[i] = get_id(R[i]);
			ll X = ps.query(1, K, 1, L[i], R[i]);
			ll Y = sf.query(1, K, 1, L[i], R[i]);
			ans = min(ans, X + Y + W[i]);
			
			// cout << X << " " << Y << " " << i << "\n";
			ps.upd(1, K, 1, C[i], X + W[i]);
			sf.upd(1, K, 1, C[i], Y + W[i]);
		}
		
		cout << (ans == INF ? -1 : ans) << "\n";
	}
}

/*

*/

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