Submission #1111805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111805		IBory	Pinball (JOI14_pinball)	C++17	100 / 100	155 ms	26812 KiB

pinball

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int SZ = 1 << 19, MAX = 100007;
ll A[MAX], B[MAX], C[MAX], W[MAX], L[MAX], R[MAX];

struct Seg {
	ll T[SZ << 1];
	Seg() {
		memset(T, 0x3f, sizeof(T));
	}
	void Update(int i, ll v) {
		i += SZ - 1;
		T[i] = min(T[i], v);
		while (i >>= 1) T[i] = min(T[i * 2], T[i * 2 + 1]);
	}
	ll Query(int L, int R, int sL = 1, int sR = SZ, int n = 1) {
		if (R < sL || sR < L) return 1e18;
		if (L <= sL && sR <= R) return T[n];
		int mid = (sL + sR) >> 1;
		return min(Query(L, R, sL, mid, n * 2), Query(L, R, mid + 1, sR, n * 2 + 1));
	}
} TL, TR;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M;
	cin >> N >> M;
	vector<int> U = {0, 1, M};
	for (int i = 1; i <= N; ++i) {
		cin >> A[i] >> B[i] >> C[i] >> W[i];
		U.push_back(A[i]);
		U.push_back(B[i]);
		U.push_back(C[i]);
	}
	
	sort(U.begin(), U.end());
	U.erase(unique(U.begin(), U.end()), U.end());
	for (int i = 1; i <= N; ++i) {
		A[i] = lower_bound(U.begin(), U.end(), A[i]) - U.begin();
		B[i] = lower_bound(U.begin(), U.end(), B[i]) - U.begin();
		C[i] = lower_bound(U.begin(), U.end(), C[i]) - U.begin();
	}

	memset(L, 0x3f, sizeof(L));
	memset(R, 0x3f, sizeof(R));
	TL.Update(1, 0);
	TR.Update(U.size() - 1, 0);
	for (int i = 1; i <= N; ++i) {
		ll ul = TL.Query(A[i], B[i]);
		ll ur = TR.Query(A[i], B[i]);
		TL.Update(C[i], L[i] = ul + W[i]);
		TR.Update(C[i], R[i] = ur + W[i]);
	}

	ll ans = 1e18;
	for (int i = 1; i <= N; ++i) ans = min(ans, L[i] + R[i] - W[i]);
	cout << (ans == 1e18 ? -1 : ans);
	return 0;
}

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