oj.uz

답안 #682550

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682550 2023-01-16T13:37:29 Z NK_ Pinball (JOI14_pinball) C++17
0 / 100
 1 ms 212 KB 
// 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);

	vector<ll> L(N), R(N), D(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]);
	}

	if (M == 1) {
		cout << 0 << nl;
		return 0;
	}
	
	sort(begin(X), end(X)); X.erase(unique(begin(X), end(X)), end(X));

	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++) {
 			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);
	}

	ll ans = INFL;
	for(int i = 0; i < N; i++) ans = min(ans, L[i] + R[i] - D[i]);

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


    return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -