Submission #991212

#	Time	Username	Problem	Language	Result	Execution time	Memory
991212		model_code	Marathon Race 2 (JOI24_ho_t3)	C++17	100 / 100	190 ms	33780 KiB

Main

/*
	FULL-SCORE SOLUTION
	- Time Complexity: O((N + Q) * log N + maxT)
*/

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

// limits the problem to "the first ball to take is the leftmost"
vector<bool> solve_oneside(int N, int L, vector<int> X, vector<int> W, int Q, vector<int> S, vector<int> G, vector<int> T) {
	// step #1. preparation
	const long long INF = 3LL << 59;
	vector<int> SW(N + 1);
	for (int i = 0; i < N; i++) {
		SW[i + 1] = SW[i] + W[i];
	}
	auto chmin = [&](long long& a, long long b) -> void {
		a = min(a, b);
	};

	// step #2. dynamic programming
	// - dp[l][r][d]: minimum time when "took balls at X[0], ..., X[l] and X[r], ..., X[N-1] and the current position is X[l] (d=0) or X[r] (d=1)"
	vector<vector<array<long long, 2> > > dp(N + 1, vector<array<long long, 2> >(N + 1, {INF, INF}));
	dp[0][N][0] = W[0];
	for (int l = 0; l <= N; l++) {
		for (int r = N; r >= l + 2; r--) {
			int balls = SW[l + 1] + (SW[N] - SW[r]); // number of carrying balls
			chmin(dp[l + 1][r][0], dp[l][r][0] + (long long)(X[l + 1] - X[l]) * (balls + 1) + W[l + 1]); // X[l] -> X[l+1]
			chmin(dp[l][r - 1][1], dp[l][r][0] + (long long)(X[r - 1] - X[l]) * (balls + 1) + W[r - 1]); // X[l] -> X[r-1]
			if (r != N) {
				chmin(dp[l + 1][r][0], dp[l][r][1] + (long long)(X[r] - X[l + 1]) * (balls + 1) + W[l + 1]); // X[r] -> X[l+1]
				chmin(dp[l][r - 1][1], dp[l][r][1] + (long long)(X[r] - X[r - 1]) * (balls + 1) + W[r - 1]); // X[r] -> X[r-1]
			}
		}
	}

	// step #3. calculate answer
	vector<bool> ans(Q, false);
	for (int i = 0; i < Q; i++) {
		int pos = lower_bound(X.begin(), X.end(), G[i] + 1) - X.begin();
		if (pos != 0) {
			long long mintime = INF;
			chmin(mintime, dp[pos - 1][pos][0] + abs(S[i] - X[0]) + (long long)(G[i] - X[pos - 1]) * (SW[N] + 1)); // S[i] -> X[0] -> ... -> X[pos-1] -> G[i]
			chmin(mintime, dp[pos - 1][pos][1] + abs(S[i] - X[0]) + (long long)(X[pos] - G[i]) * (SW[N] + 1)); // S[i] -> X[0] -> ... -> X[pos] -> G[i]
			ans[i] = (mintime <= T[i]);
		}
	}

	return ans;
}

// solve function
vector<bool> solve(int N, int L, vector<int> X, int Q, vector<int> S, vector<int> G, vector<int> T) {
	// step #1. compression
	vector<int> SX = X;
	sort(SX.begin(), SX.end());
	vector<int> CX = SX;
	CX.erase(unique(CX.begin(), CX.end()), CX.end());
	int CN = CX.size();
	int cur = 0;
	vector<int> W(CN);
	for (int i = 0; i < CN; i++) {
		while (cur != N && SX[cur] == CX[i]) {
			W[i] += 1;
			cur += 1;
		}
	}

	// step #2. consider limit (1+2+3+4+...)
	int maxT = *max_element(T.begin(), T.end());
	if ((long long)(CN) * (CN + 1) / 2 > maxT) {
		return vector<bool>(Q, false);
	}
	
	// step #3. consider two directions
	vector<bool> ans(Q, false);
	for (int i = 0; i < 2; i++) {
		// get answer
		vector<bool> res = solve_oneside(CN, L, CX, W, Q, S, G, T);
		for (int j = 0; j < Q; j++) {
			ans[j] = ans[j] || res[j];
		}
		// reverse
		for (int j = 0; j < CN; j++) {
			CX[j] = L - CX[j];
		}
		reverse(CX.begin(), CX.end());
		reverse(W.begin(), W.end());
		for (int j = 0; j < Q; j++) {
			S[j] = L - S[j];
			G[j] = L - G[j];
		}
	}

	return ans;
}

int main() {
	// input
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, L;
	cin >> N >> L;
	vector<int> X(N);
	for (int i = 0; i < N; i++) {
		cin >> X[i];
	}
	int Q;
	cin >> Q;
	vector<int> S(Q), G(Q), T(Q);
	for (int i = 0; i < Q; i++) {
		cin >> S[i] >> G[i] >> T[i];
	}

	// output
	vector<bool> ans = solve(N, L, X, Q, S, G, T);
	for (int i = 0; i < Q; i++) {
		cout << (ans[i] ? "Yes\n" : "No\n");
	}

	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 28 / 28
• Subtask 5: 10 / 10
• Subtask 6: 19 / 19
• Subtask 7: 19 / 19