結果
| 問題 |
No.448 ゆきこーだーの雨と雪 (3)
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:03:02 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 118 ms / 2,000 ms |
| コード長 | 12,120 bytes |
| コンパイル時間 | 670 ms |
| コンパイル使用メモリ | 83,960 KB |
| 実行使用メモリ | 18,048 KB |
| 最終ジャッジ日時 | 2025-05-14 13:04:23 |
| 合計ジャッジ時間 | 5,806 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 35 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Define long long type for large numbers
typedef long long ll;
// Use a sufficiently large value for infinity. Maximum possible sum is N * maxD ~ 2e5 * 1e9 = 2e14.
// 4e18 ensures it's larger than any possible sum and fits within 64-bit signed integer.
const ll INF = 4e18;
// Structure to hold task information
struct Task {
ll T, D; // Time and Difficulty
};
/**
* @brief Check function to determine if it's possible to assign tasks such that
* Ame only performs tasks with difficulty <= X, respecting Yuki's cooldown K.
*
* @param X The maximum difficulty threshold for Ame.
* @param N The number of tasks.
* @param K Yuki's required rest time (cooldown).
* @param tasks Vector of tasks sorted by time.
* @return true if such an assignment is possible, false otherwise.
*/
bool check(ll X, int N, ll K, const vector<Task>& tasks) {
// Tracks the time Yuki finished her last assigned task. Use -INF to represent initial state.
ll last_yuki_task_time = -INF;
for (int i = 0; i < N; ++i) {
ll Ti = tasks[i].T;
ll Di = tasks[i].D;
// Check if Ame can perform this task based on difficulty threshold X
bool ame_possible = (Di <= X);
// Check if Yuki is available to perform this task
bool yuki_available;
if (last_yuki_task_time == -INF) {
yuki_available = true; // Yuki is always available initially
} else {
// Check if current task time Ti is at least K time units after Yuki's last task finish time.
// Use subtraction `Ti - K >= last_yuki_task_time` to avoid potential overflow with `last_yuki_task_time + K` if K is very large.
if (last_yuki_task_time > Ti) { // Optimization: if last Yuki task was later than current task time
yuki_available = false; // Technically impossible, but helps with large K.
} else if (K > Ti) { // K is larger than current time, Ti - K could underflow. Handle carefully.
if (last_yuki_task_time <= Ti - K) { // If Ti - K is negative, this comparison works correctly
yuki_available = true;
} else {
yuki_available = false;
}
}
else if (Ti - K >= last_yuki_task_time) {
yuki_available = true;
} else {
yuki_available = false;
}
}
if (!ame_possible) { // Task difficulty Di > X, Ame cannot perform it.
if (!yuki_available) {
// Yuki must perform the task, but she's unavailable. Impossible state.
return false;
}
// Yuki must perform the task and she is available. Update her last task time.
last_yuki_task_time = Ti;
} else { // Task difficulty Di <= X, Ame can perform it.
if (!yuki_available) {
// Ame must perform task i because Yuki is unavailable.
// Yuki's last task time remains unchanged.
} else {
// Both Ame and Yuki can perform the task.
// The check function aims for feasibility. To maximize future feasibility, we should keep Yuki available as much as possible.
// This translates to minimizing the `last_yuki_task_time` state variable.
// If Ame performs the task, Yuki's state remains `last_yuki_task_time`.
// If Yuki performs the task, Yuki's state becomes `Ti`.
// We choose the action that results in the minimum `last_yuki_task_time`.
if (Ti <= last_yuki_task_time) {
// If assigning to Yuki results in an earlier or same availability time, choose Yuki.
last_yuki_task_time = Ti;
}
// else { // Assigning to Ame keeps the earlier availability time. State remains `last_yuki_task_time`. No state change needed. }
}
}
}
// If all tasks could be assigned respecting constraints, return true.
return true;
}
// Segment tree structure for Range Minimum Query
struct Node {
ll val;
Node() : val(INF) {} // Initialize nodes with infinity
};
vector<Node> tree; // Segment tree storage
int N_seg; // Size of the segment tree base array = N+1
// Build segment tree recursively
void build(int node, int start, int end) {
if (start == end) {
// Initialize leaf node 0 (base case before any tasks) with value 0, others with INF
tree[node].val = (start == 0) ? 0 : INF;
} else {
int mid = start + (end - start) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
// Internal node stores the minimum of its children
tree[node].val = min(tree[2 * node].val, tree[2 * node + 1].val);
}
}
// Update segment tree at index idx with value
void update(int node, int start, int end, int idx, ll value) {
// Check if index is valid for current node range
if (idx < start || idx > end) return;
if (start == end) { // Leaf node found
tree[node].val = value;
} else {
int mid = start + (end - start) / 2;
if (idx <= mid) { // Index is in the left child range
update(2 * node, start, mid, idx, value);
} else { // Index is in the right child range
update(2 * node + 1, mid + 1, end, idx, value);
}
// Update internal node value after child update
tree[node].val = min(tree[2 * node].val, tree[2 * node + 1].val);
}
}
// Query minimum value in range [l, r]
ll query(int node, int start, int end, int l, int r) {
// If query range is invalid or outside current node range, return INF
if (r < start || end < l || l > r) {
return INF;
}
// If current node range is fully contained within query range, return node value
if (l <= start && end <= r) {
return tree[node].val;
}
// Recursively query children and return minimum
int mid = start + (end - start) / 2;
ll p1 = query(2 * node, start, mid, l, r);
ll p2 = query(2 * node + 1, mid + 1, end, l, r);
return min(p1, p2);
}
int main() {
// Faster I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of tasks
ll K; // Yuki's cooldown time
cin >> N >> K;
vector<Task> tasks(N);
ll maxD = 0; // Keep track of maximum difficulty for binary search range
for (int i = 0; i < N; ++i) {
cin >> tasks[i].T >> tasks[i].D;
maxD = max(maxD, tasks[i].D);
}
ll low = 0, high = maxD, min_max_diff = -1; // Binary search range for minimum max difficulty M
// Check if M=0 is possible first
bool M0_possible = check(0, N, K, tasks);
if (M0_possible) {
min_max_diff = 0; // If M=0 possible, that's the minimum possible M
} else {
// If M=0 not possible, binary search for the smallest M > 0
low = 1; // Start search from 1
while (low <= high) {
ll mid = low + (high - low) / 2;
if (mid == 0) { // Safety check, should not occur if low starts at 1
low = 1; continue;
}
if (check(mid, N, K, tasks)) {
min_max_diff = mid; // Found a possible M, try smaller
high = mid - 1;
} else {
low = mid + 1; // mid is too small, need larger M
}
}
}
// If M=0 is the answer, output 0 0 and exit
if (min_max_diff == 0) {
cout << 0 << endl;
cout << 0 << endl;
return 0;
}
// If binary search failed to find any valid M > 0 (min_max_diff still -1), it indicates an issue.
// However, check(maxD) should always be true if N>=1, guaranteeing a solution M exists.
// This path should theoretically not be reached under problem constraints.
if (min_max_diff == -1) {
// This case shouldn't happen with N>=1. Maybe output error or default?
// Let's assume problem guarantees solution existence.
min_max_diff = maxD; // Fallback? Or maybe it implies check(maxD) itself failed?
}
// Calculate Minimum Total Difficulty S for the found M = min_max_diff using DP with Segment Tree optimization
vector<ll> dpA(N + 1, INF); // dpA[i] min cost ending with Ame doing task i-1
vector<ll> dpY(N + 1, INF); // dpY[i] min cost ending with Yuki doing task i-1
dpA[0] = 0; dpY[0] = 0; // Base case: cost is 0 before any task
// Precompute prefix sums of difficulties
vector<ll> PS_D(N + 1, 0);
for(int k = 0; k < N; ++k) { PS_D[k+1] = PS_D[k] + tasks[k].D; }
// Precompute last invalid task index for each task i
// prev_invalid_0based[i] = largest index p < i s.t. tasks[p].D > M. If none, -1.
vector<int> prev_invalid_0based(N, -1);
int last_invalid = -1;
for(int k = 0; k < N; ++k) {
prev_invalid_0based[k] = last_invalid;
if (tasks[k].D > min_max_diff) { last_invalid = k; }
}
// Setup segment tree for DP optimization
N_seg = N + 1; // Need states 0 to N
tree.resize(4 * N_seg);
build(1, 0, N_seg - 1); // Build tree, initializes state 0 value
int p_idx = -1; // Two pointer: Max 0-based task index j such that T_j <= T_i - K
// Main DP loop
for (int i = 0; i < N; ++i) { // Process tasks 0 to N-1
ll Ti = tasks[i].T;
ll Di = tasks[i].D;
// Calculate dpA[i+1]: Minimum cost if Ame does task i
if (Di <= min_max_diff) { // Ame can only do task i if difficulty <= M
ll prev_cost = min(dpA[i], dpY[i]); // Cost up to task i-1
if (prev_cost != INF) { dpA[i+1] = prev_cost + Di; }
} // else dpA[i+1] remains INF
// Calculate dpY[i+1]: Minimum cost if Yuki does task i
// Update two pointer `p_idx` to find the largest index j such that tasks[j].T <= Ti - K
while (p_idx + 1 < i && tasks[p_idx + 1].T <= Ti - K) {
p_idx++;
}
int idx_max = p_idx; // largest valid index j for Yuki's previous task
// Minimum cost transitioning from a state where Yuki did task j >= 0
ll cost_from_j = INF;
// Query range for state index k = j+1: starts after last invalid task, ends at max valid j+1 index.
int query_l = prev_invalid_0based[i] + 1;
int query_r = idx_max + 1;
if (query_l <= query_r) { // Ensure query range is valid
// Query segment tree for min(mcost[k] - PS_D[k]) in range [query_l, query_r]
ll min_V_k = query(1, 0, N_seg - 1, query_l, query_r);
if (min_V_k != INF) {
// The DP transition: dpY[i+1] = PS_D[i] + min_V_k
cost_from_j = PS_D[i] + min_V_k;
}
}
// Minimum cost transitioning from the initial state (j=-1, state index 0)
ll cost_from_neg1 = INF;
// This transition is valid only if no task k in [0, i-1] has difficulty > M
if (prev_invalid_0based[i] == -1) {
cost_from_neg1 = PS_D[i]; // Cost is sum of D_k for k=0..i-1 starting from state 0 (cost 0)
}
// dpY[i+1] is the minimum of the two possible transitions
dpY[i+1] = min(cost_from_j, cost_from_neg1);
// Update segment tree with the value for state i+1 (after task i)
ll mcost_i1 = min(dpA[i+1], dpY[i+1]); // minimum cost after task i
if (mcost_i1 != INF) {
// Update tree at index i+1 with value mcost[i+1] - PS_D[i+1]
update(1, 0, N_seg - 1, i + 1, mcost_i1 - PS_D[i+1]);
} // else: If state i+1 is unreachable (INF), no need to update, segtree node remains INF.
}
// Final answer is the minimum cost after processing all N tasks
ll min_total_diff = min(dpA[N], dpY[N]);
// Output the results
cout << min_max_diff << endl;
cout << min_total_diff << endl;
return 0;
}