Submission #682539

#	Time	Username	Problem	Language	Result	Execution time	Memory
682539		NK_	Pinball (JOI14_pinball)	C++17	0 / 100	1 ms	328 KiB

pinball

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

using ll = long long;

const ll INFL = ll(1e18) + 10;

struct Seg {
	const ll ID = INFL; ll comb(ll a, ll b) { return min(a, b); }
	vector<ll> seg; int n;
	void init(int _n) {
		n = _n;
		seg.assign(2*n, ID);
	}

	void pull(int x) { seg[x] = comb(seg[2*x], seg[2*x+1]); }

	void set(int p, ll x) {
		p += n; seg[p] = min(seg[p], x); for(p /= 2; p; p /= 2) pull(p);
	}

	ll query(int l, int r) {
		ll ra, rb; ra = rb = ID;
		for(l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra, seg[l++]);
			if (r&1) rb = comb(seg[--r], rb);
		}
		return comb(ra, rb);
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; cin >> N >> M;
	vector<int> A(N), B(N), C(N), D(N);

	vector<ll> L(N), R(N);
	vector<int> X;
	for(int i = 0; i < N; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		--A[i], --B[i], --C[i];
		X.push_back(A[i]); X.push_back(B[i]); X.push_back(C[i]);
	}

	sort(begin(X), end(X)); X.erase(unique(begin(X), end(X)), end(X));

	vector<int> a = A, b = B, c = C;

	for(auto &x : a) x = lower_bound(begin(X), end(X), x) - begin(X);
	for(auto &x : b) x = lower_bound(begin(X), end(X), x) - begin(X);
	for(auto &x : c) x = lower_bound(begin(X), end(X), x) - begin(X);

	int K = size(X);

	for(int t = 0; t < 2; t++) {

		Seg st; st.init(K);
		st.set(0, 0);
 		for(int i = 0; i < N; i++) {
 			// cout << i << " -> " << a[i] << " " << b[i] << " " << c[i] << endl;

 			L[i] = st.query(a[i], b[i]) + D[i];
 			st.set(c[i], L[i]);

 			a[i] = K-1-a[i];
 			b[i] = K-1-b[i];
 			c[i] = K-1-c[i];
 			swap(a[i], b[i]);
 		}

 		L.swap(R);
	}

		
	vector<vector<int>> I(K);
	ll ans = INFL;
	for(int i = 0; i < N; i++) {
		I[c[i]].push_back(i);
		ans = min(ans, L[i] + R[i] - D[i]);
	}


	for(auto v : I) if (size(v) > 0) {
		multiset<ll> l, r;
		for(auto i : v) {
			l.insert(L[i]);
			r.insert(R[i]);
		}
		ans = min(ans, *begin(l) + *begin(r));
	}

	cout << (ans == INFL ? -1 : ans) << nl;


    return 0;
}

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