結果
| 問題 |
No.1982 [Cherry 4th Tune B] 絶険
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:16:05 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,976 ms / 3,000 ms |
| コード長 | 10,650 bytes |
| コンパイル時間 | 1,751 ms |
| コンパイル使用メモリ | 112,432 KB |
| 実行使用メモリ | 134,292 KB |
| 最終ジャッジ日時 | 2025-05-14 13:17:52 |
| 合計ジャッジ時間 | 28,492 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 35 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <functional> // Required for std::function
using namespace std;
// Use long long for potentially large heights and sums
typedef long long ll;
// Structure to store operation details relevant for segment tree nodes
// We only need the operation index k and its height H within the segment tree structure
// The color C is stored separately in a global map keyed by k.
struct SegTreeOp {
int k; // Original operation index 1..K
ll H; // Height added by this operation
};
// Data associated with each operation k (stored globally)
struct OpData {
int C; // Color
ll H; // Height (stored here for convenience, also derivable from SegTreeOp)
};
// Segment tree nodes store a list of operations affecting their range
vector<vector<SegTreeOp>> tree_ops;
// For each node, store prefix sums of heights H of its operations (sorted by k)
// This allows efficient querying of cumulative height up to a certain k_mid
vector<vector<ll>> tree_prefix_H;
// Global map storing details (Color, Height) for each operation k, accessible by k
map<int, OpData> ops_data;
// Stores the size of the segment tree base layer (a power of 2 >= N)
int N_segtree;
// Initializes the segment tree structure based on number of blocks N
// The tree will cover indices 1 to N_segtree.
void build_tree(int N) {
N_segtree = 1;
while (N_segtree < N) N_segtree *= 2;
// Resize vectors to hold data for 2*N_segtree nodes. Nodes are 1-indexed.
tree_ops.resize(2 * N_segtree);
tree_prefix_H.resize(2 * N_segtree);
}
// Internal recursive function to add an operation to the segment tree
// Adds operation k with height H to the appropriate nodes covering the range [L, R]
void add_op_internal(int k, ll H, int L, int R, int node, int node_L, int node_R) {
// If the node's range [node_L, node_R] is completely outside the operation's range [L, R], do nothing.
if (R < node_L || L > node_R) {
return;
}
// If the node's range is fully contained within the operation's range,
// store the operation (k, H) at this node. This is the standard segment tree range update approach.
if (L <= node_L && node_R <= R) {
tree_ops[node].push_back({k, H});
return;
}
// Otherwise, the operation's range partially overlaps the node's range. Recurse down to children.
int mid = node_L + (node_R - node_L) / 2;
add_op_internal(k, H, L, R, 2 * node, node_L, mid); // Recurse on left child
add_op_internal(k, H, L, R, 2 * node + 1, mid + 1, node_R); // Recurse on right child
}
// Public function to add an operation
// Stores operation details (C, H) globally in ops_data map keyed by k.
// Calls internal function to update the segment tree structure.
void add_op(int k, int L, int R, int C, ll H) {
ops_data[k] = {C, H};
add_op_internal(k, H, L, R, 1, 1, N_segtree); // Start update from root node 1 covering range [1, N_segtree]
}
// Query the cumulative height at block I from operations with index <= k_mid
// Internal recursive function used by query_total_H
ll query_sum_H_internal(int I, int k_mid, int node, int node_L, int node_R) {
ll current_sum = 0;
// If this node stores operations
if (!tree_ops[node].empty()) {
// Operations in tree_ops[node] are sorted by k after finalization phase.
// Use binary search (upper_bound) to find the first operation with index k > k_mid.
auto it = upper_bound(tree_ops[node].begin(), tree_ops[node].end(), k_mid, [](int val, const SegTreeOp& op) {
return val < op.k;
});
// The number of operations with k <= k_mid is the distance from the beginning to the iterator 'it'.
int count = distance(tree_ops[node].begin(), it);
// If there are such operations (count > 0), use the precomputed prefix sum.
// tree_prefix_H[node][count] gives the sum of H for the first 'count' operations.
if (count > 0) {
current_sum = tree_prefix_H[node][count];
}
}
// Base case: If this is a leaf node (represents a single block)
if (node_L == node_R) {
// We have reached the leaf corresponding to block I (or some other leaf if I is not node_L)
// The sum accumulated from operations stored at ancestor nodes and this leaf node is returned.
return current_sum;
}
// Recursive step: If it's an internal node, determine which child contains block I and recurse.
int mid = node_L + (node_R - node_L) / 2;
if (I <= mid) {
// Block I is in the left child's range. Add the sum from the recursive call on the left child.
return current_sum + query_sum_H_internal(I, k_mid, 2 * node, node_L, mid);
} else {
// Block I is in the right child's range. Add the sum from the recursive call on the right child.
return current_sum + query_sum_H_internal(I, k_mid, 2 * node + 1, mid + 1, node_R);
}
}
// Public function to query total cumulative height at block I considering operations up to index K_max
ll query_total_H(int I, int K_max) {
// If K_max is 0 (no operations considered), the height is 0.
if (K_max == 0) return 0;
// Call the internal recursive query function starting from the root node (1) which covers the range [1, N_segtree].
return query_sum_H_internal(I, K_max, 1, 1, N_segtree);
}
int main() {
// Optimize standard I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of blocks
int K; // Number of operations
int Q; // Number of queries
cin >> N >> K >> Q;
// Initialize the segment tree structure based on N
build_tree(N);
// Read and process all K operations, adding them to the segment tree
for (int k = 1; k <= K; ++k) {
int L, R, C;
ll H;
cin >> L >> R >> C >> H;
add_op(k, L, R, C, H);
}
// Finalize the segment tree after all operations have been added.
// This crucial step sorts operations within each node by their index k
// and precomputes prefix sums of their heights H for efficient querying later.
// Uses a Depth First Search (DFS) traversal implemented with std::function.
function<void(int)> finalize_recursive =
[&](int node) {
// If the current node has operations stored
if (!tree_ops[node].empty()) {
// Sort the operations based on their original index k
sort(tree_ops[node].begin(), tree_ops[node].end(), [](const SegTreeOp& a, const SegTreeOp& b) {
return a.k < b.k;
});
// Resize prefix sum vector and compute prefix sums.
// tree_prefix_H[node][i] stores the sum of H for the first i operations in the sorted list.
tree_prefix_H[node].resize(tree_ops[node].size() + 1, 0);
for (size_t i = 0; i < tree_ops[node].size(); ++i) {
tree_prefix_H[node][i + 1] = tree_prefix_H[node][i] + tree_ops[node][i].H;
}
}
// Check if the node is an internal node before recursing.
// An efficient check is `2 * node + 1 < tree_ops.size()`, ensuring right child index is valid.
if (2 * node + 1 < tree_ops.size()) {
finalize_recursive(2 * node); // Recurse on left child
finalize_recursive(2 * node + 1); // Recurse on right child
}
};
// Only run the finalization process if there were any operations (K > 0)
if (K > 0)
finalize_recursive(1); // Start DFS finalization from the root node 1
// Process Q queries
for (int q = 0; q < Q; ++q) {
int I; // Block index for the query
ll X; // Target height check value from the query
cin >> I >> X;
// Problem statement guarantees 1 <= X_q. Check for X <= 0 just for robustness.
if (X <= 0) {
cout << -1 << "\n";
continue;
}
// Calculate the total height of the wall at block I after all K operations are applied.
ll total_H = query_total_H(I, K);
// The query asks for color at height X-0.5. This position exists only if total height >= X.
// If the target height X is strictly greater than the total wall height, output -1.
if (total_H < X) {
cout << -1 << "\n";
continue;
}
// Perform binary search on the operation index k \in [1, K] to find the *minimal* k*
// such that the cumulative height at block I after operations up to k* is at least X.
// This k* corresponds to the operation that builds the wall segment containing height X-0.5.
int low = 1, high = K, ans_k = -1; // Initialize ans_k to -1 (sentinel for not found)
while (low <= high) {
// Calculate midpoint, avoiding potential overflow
int mid = low + (high - low) / 2;
// Safety check: mid should be at least 1 since low starts at 1. Skip if mid=0 somehow occurs.
if (mid == 0) {
low = 1; continue;
}
// Calculate cumulative height at block I considering operations up to index mid
ll current_total_H = query_total_H(I, mid);
// Check if the cumulative height reaches or exceeds X
if (current_total_H >= X) {
// If height is sufficient (>= X), then operation 'mid' *might* be the answer k*.
// Record 'mid' as a potential answer and try searching for smaller k values (in range [low, mid-1]).
ans_k = mid;
high = mid - 1;
} else {
// If height is insufficient (< X), we need operations with larger indices k.
// Search in the higher range [mid+1, high].
low = mid + 1;
}
}
// After binary search, ans_k holds the minimal k* that satisfies the condition.
// If total_H >= X >= 1 and K > 0, we are guaranteed to find such a k*.
if (ans_k == -1) {
// This case should ideally not be reached under problem constraints if K>0.
// If K=0, the `total_H < X` check handles it. Output -1 as a fallback/error indicator.
cout << -1 << "\n";
} else {
// The color at height X-0.5 is determined by the operation with index ans_k.
// Retrieve the color C from the global ops_data map using ans_k.
cout << ops_data[ans_k].C << "\n";
}
}
return 0;
}