Submission #301654

#	Time	Username	Problem	Language	Result	Execution time	Memory
301654		E869120	Pinball (JOI14_pinball)	C++14	29 / 100	2 ms	512 KiB

pinball

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

class RangeMin {
	public:
	int size_ = 1;
	vector<long long> dat;
	
	void init(int sz) {
		while (size_ <= sz) size_ *= 2;
		dat.resize(size_ * 2, 0);
	}
	void update(int pos, long long x) {
		pos += size_;
		dat[pos] = x;
		while (pos >= 2) {
			pos >>= 1;
			dat[pos] = min(dat[pos * 2], dat[pos * 2 + 1]);
		}
	}
	long long query_(int l, int r, int a, int b, int u) {
		if (l <= a && b <= r) return dat[u];
		if (r <= a || b <= l) return (1LL << 60);
		long long v1 = query_(l, r, a, (a + b) >> 1, u * 2);
		long long v2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		return min(v1, v2);
	}
	long long query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

long long N, L;
long long A[1 << 19], B[1 << 19], C[1 << 19], D[1 << 19];
long long dpl[1 << 19];
long long dpr[1 << 19];
RangeMin ZL, ZR;
vector<long long> X;

int main() {
	// INPUT
	cin >> N >> L;
	for (int i = 0; i < N; i++) cin >> A[i] >> B[i] >> C[i] >> D[i];
	
	// ZAATS
	for (int i = 0; i < N; i++) X.push_back(A[i]);
	for (int i = 0; i < N; i++) X.push_back(B[i]);
	for (int i = 0; i < N; i++) X.push_back(C[i]);
	X.push_back(1);
	X.push_back(L + 1);
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	for (int i = 0; i < N; i++) A[i] = lower_bound(X.begin(), X.end(), A[i]) - X.begin();
	for (int i = 0; i < N; i++) B[i] = lower_bound(X.begin(), X.end(), B[i] + 1) - X.begin();
	for (int i = 0; i < N; i++) C[i] = lower_bound(X.begin(), X.end(), C[i]) - X.begin();
	
	// PRCLC
	long long Answer = (1LL << 60);
	ZL.init(X.size() + 2);
	ZR.init(X.size() + 2);
	for (int i = 0; i < (int)X.size(); i++) dpl[i] = (1LL << 60);
	for (int i = 0; i < (int)X.size(); i++) dpr[i] = (1LL << 60);
	dpl[0] = 0;
	dpr[X.size() - 2] = 0;
	for (int i = 0; i < (int)X.size(); i++) ZL.update(i, dpl[i]);
	for (int i = 0; i < (int)X.size(); i++) ZR.update(i, dpr[i]);
	
	// CALCS
	for (int i = 0; i < N; i++) {
		long long val1 = ZL.query(A[i], B[i]);
		long long val2 = ZR.query(A[i], B[i]);
		Answer = min(Answer, val1 + val2 + D[i]);
		dpl[C[i]] = min(dpl[C[i]], val1 + D[i]);
		dpr[C[i]] = min(dpr[C[i]], val2 + D[i]);
		ZL.update(C[i], dpl[C[i]]);
		ZR.update(C[i], dpr[C[i]]);
		//cout << val1 << " " << val2 << endl;
	}
	
	// FINAL
	if (Answer == (1LL << 60)) cout << "-1" << endl;
	else cout << Answer << endl;
	return 0;
}

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