結果
| 問題 |
No.1982 [Cherry 4th Tune B] 絶険
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:03:45 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 11,627 bytes |
| コンパイル時間 | 1,110 ms |
| コンパイル使用メモリ | 75,704 KB |
| 実行使用メモリ | 815,396 KB |
| 最終ジャッジ日時 | 2025-05-14 13:05:48 |
| 合計ジャッジ時間 | 23,425 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 23 MLE * 7 -- * 5 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:164:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
164 | scanf("%d %d %d", &N_input, &K_input, &Q_input);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:168:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
168 | scanf("%d %d %d %lld", &L_ops[k], &R_ops[k], &C_ops[k], &H_ops[k]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:172:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
172 | scanf("%d %lld", &IQ_queries[q], &XQ_queries[q]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <cstdio> // Use C-style IO for potentially faster execution
using namespace std;
// Define type for long long integers
typedef long long ll;
// Constants based on problem constraints
const int MAXN_Q = 200005; // Maximum N (number of sections) and Q (number of queries)
const int MAXK = 200005; // Maximum K (number of operations)
// Input variables declaration
int N_input, K_input, Q_input; // Number of sections, operations, queries
int L_ops[MAXK], R_ops[MAXK], C_ops[MAXK]; // Parameters for K operations: Left section, Right section, Color
ll H_ops[MAXK]; // Height for K operations
int IQ_queries[MAXN_Q]; // Section index for Q queries
ll XQ_queries[MAXN_Q]; // Target height X_q for Q queries
// Node structure for the Persistent Segment Tree
struct Node {
ll sum = 0; // Sum of heights in the node's range
ll lazy = 0; // Lazy tag for pending updates
int left = 0; // Index of the left child node in the `nodes` pool (0 means null)
int right = 0; // Index of the right child node in the `nodes` pool (0 means null)
};
vector<Node> nodes; // Node pool implemented as a vector
int node_idx = 0; // Counter for allocated nodes, points to the next available index in the `nodes` pool
// Function to create a new node in the pool
// It copies the state from a `template_node_idx` (default is 0, the dummy node)
// Returns the index of the newly created node
int newNode(int template_node_idx = 0) {
// vector `push_back` automatically handles resizing if needed
nodes.push_back(nodes[template_node_idx]);
// Increment node counter and return the index of the newly added node
return ++node_idx;
}
// Function to propagate lazy tags downwards from `node_p` covering range [l, r]
// This is essential for lazy propagation in segment trees
void push(int node_p, int l, int r) {
// If the node has no pending lazy update or it's a leaf node, return
if (nodes[node_p].lazy == 0 || l == r) {
return;
}
ll lazy_val = nodes[node_p].lazy; // Get the lazy value to propagate
int m = l + (r - l) / 2; // Calculate midpoint for splitting range
// Get the indices of the current children (these act as templates for new children)
int current_left = nodes[node_p].left;
int current_right = nodes[node_p].right;
// Create a new left child node by copying the template state
nodes[node_p].left = newNode(current_left);
// Apply the lazy value to the new left child's sum
// Use (ll) cast to ensure multiplication is done using long long
nodes[nodes[node_p].left].sum += lazy_val * (ll)(m - l + 1);
// Add the lazy value to the new left child's lazy tag for further propagation
nodes[nodes[node_p].left].lazy += lazy_val;
// Create a new right child node similarly
nodes[node_p].right = newNode(current_right);
// Apply lazy value to the new right child's sum
nodes[nodes[node_p].right].sum += lazy_val * (ll)(r - (m + 1) + 1);
// Add lazy value to the new right child's lazy tag
nodes[nodes[node_p].right].lazy += lazy_val;
// Clear the lazy tag of the current node since it has been propagated
nodes[node_p].lazy = 0;
}
// Function to perform a range update on the segment tree
// Adds 'value' to all elements in the range [target_L, target_R]
// Based on persistent node `node_p` covering range [l, r]
// Creates new nodes along the path (persistence)
// Returns the index of the new root node of the updated subtree
int update(int node_p, int l, int r, int target_L, int target_R, ll value) {
// Create a new node for the current position on the path, copying state from `node_p`
int new_node_p = newNode(node_p);
// Case 1: The current node's range [l, r] is fully contained within the target range [target_L, target_R]
if (target_L <= l && r <= target_R) {
// Apply the update directly to this node's sum and lazy tag
nodes[new_node_p].sum += value * (ll)(r - l + 1); // Use (ll) cast for safety
nodes[new_node_p].lazy += value;
// Return the index of this updated node
return new_node_p;
}
// Case 2: Partial overlap or no overlap. Need to recurse.
// First, push down any pending lazy updates from the *new* node before recursing.
push(new_node_p, l, r);
int m = l + (r - l) / 2; // Midpoint for splitting range
// If the target range overlaps with the left child's range [l, m]
if (target_L <= m) {
// Recursively update the left child. The returned index is the new left child.
nodes[new_node_p].left = update(nodes[new_node_p].left, l, m, target_L, target_R, value);
}
// If the target range overlaps with the right child's range [m+1, r]
if (target_R > m) {
// Recursively update the right child. The returned index is the new right child.
nodes[new_node_p].right = update(nodes[new_node_p].right, m + 1, r, target_L, target_R, value);
}
// After potential updates to children, recalculate the sum for the current node
// The sum is based on the sums of its potentially updated children.
nodes[new_node_p].sum = nodes[nodes[new_node_p].left].sum + nodes[nodes[new_node_p].right].sum;
// Return the index of this updated node
return new_node_p;
}
// Function to query the value (total height) at a specific point `target_idx`
// Uses the segment tree rooted at `node_p` covering range [l, r]
ll query_simple(int node_p, int l, int r, int target_idx) {
// Base case: Reached the leaf node corresponding to `target_idx`
if (l == r) {
// The sum at the leaf node already incorporates all propagated lazy updates
return nodes[node_p].sum;
}
// Before recursing, push down any pending lazy updates from the current node
push(node_p, l, r);
int m = l + (r - l) / 2; // Midpoint
// Decide which child path to follow based on `target_idx`
if (target_idx <= m) {
// Query the left child
return query_simple(nodes[node_p].left, l, m, target_idx);
} else {
// Query the right child
return query_simple(nodes[node_p].right, m + 1, r, target_idx);
}
}
// Stores the root indices for each version of the persistent segment tree (k=0 to K)
vector<int> roots;
// Function to build the initial segment tree structure (representing state with all heights 0)
// Recursively builds the tree for range [l, r]
// Returns the index of the root node of the built subtree.
int build(int l, int r) {
// Create a node with default values (sum=0, lazy=0, children=0)
int node_p = newNode();
// Base case: If it's a leaf node
if (l == r) {
return node_p;
}
// Recursive step: Build left and right children
int m = l + (r - l) / 2;
nodes[node_p].left = build(l, m);
nodes[node_p].right = build(m + 1, r);
// Initial sum is 0, no need to combine children sums yet.
return node_p;
}
int main() {
// Read N, K, Q using scanf
scanf("%d %d %d", &N_input, &K_input, &Q_input);
// Read K operations' parameters
for (int k = 1; k <= K_input; ++k) {
scanf("%d %d %d %lld", &L_ops[k], &R_ops[k], &C_ops[k], &H_ops[k]);
}
// Read Q queries' parameters
for (int q = 1; q <= Q_input; ++q) {
scanf("%d %lld", &IQ_queries[q], &XQ_queries[q]);
}
// Pre-allocate memory for the node pool to avoid reallocations during updates
// Estimate max nodes needed: O(N + K log N). With N, K = 2e5, logN ~ 18. Roughly 8 million nodes needed.
nodes.reserve(8000000);
// Add a dummy node at index 0. Node indices used will be >= 1.
nodes.emplace_back();
node_idx = 0; // Reset node counter after adding dummy node
// Resize the `roots` vector to hold K+1 root indices
roots.resize(K_input + 1);
// Build the initial tree (version 0) representing the state before any operations
roots[0] = build(1, N_input);
// Build the persistent segment tree versions by applying operations k=1 to K
for (int k = 1; k <= K_input; ++k) {
// Constraint H_k >= 1 ensures H_ops[k] > 0. Update only if H_k > 0.
// Create version k based on version k-1 by applying the k-th operation's update
roots[k] = update(roots[k-1], 1, N_input, L_ops[k], R_ops[k], H_ops[k]);
}
// Process the Q queries
for (int q = 1; q <= Q_input; ++q) {
int iq = IQ_queries[q]; // Section index for the current query
ll xq = XQ_queries[q]; // Target height X_q for the current query
// We are interested in height X_q - 0.5.
// Compare cumulative heights with this value. To avoid floats, we use integer arithmetic:
// Compare 2 * CumulativeHeight with 2 * (X_q - 0.5) = 2*X_q - 1.
ll target_Y = 2 * xq - 1;
// Check edge case where target height is below ground level (X_q < 1 implies target_Y < 1).
// Problem constraints state X_q >= 1, so target_Y >= 1. This check is defensive.
if (target_Y <= 0) {
printf("-1\n");
continue;
}
// Query the total height at section `iq` after all K operations (using tree version K)
ll total_height = query_simple(roots[K_input], 1, N_input, iq);
// Check if the target height (X_q - 0.5) is above the final total wall height
// Equivalent to checking if 2 * total_height < target_Y
if (2 * total_height < target_Y) {
// Target height is unreachable
printf("-1\n");
continue;
}
// Binary search over operation indices [1, K] to find the *minimal* k* such that
// the cumulative height at section `iq` after operation k* is >= X_q - 0.5.
// This is equivalent to finding minimal k* such that 2 * Height(iq, k*) >= target_Y.
int low = 1, high = K_input;
int ans_k = 0; // Initialize answer k* to 0 (indicates not found yet)
while (low <= high) {
int mid = low + (high - low) / 2; // Calculate midpoint safely
// Query cumulative height at section `iq` after `mid` operations (using tree version `mid`)
ll current_height_sum = query_simple(roots[mid], 1, N_input, iq);
// Check if the height threshold is met or exceeded
if (2 * current_height_sum >= target_Y) {
// Found a potential candidate operation index `mid`. Store it.
ans_k = mid;
// Try to find an even earlier operation (smaller index) by searching in the left half [low, mid-1]
high = mid - 1;
} else {
// Height threshold not met. Need operations with larger indices. Search in the right half [mid+1, high]
low = mid + 1;
}
}
// After binary search, `ans_k` holds the index of the operation that first pushed the height >= X_q - 0.5.
// If the initial total_height check passed, ans_k should be found and > 0.
if (ans_k > 0) {
// Print the color associated with operation `ans_k`
printf("%d\n", C_ops[ans_k]);
} else {
// This case theoretically shouldn't happen if the total height check passed and total height > 0.
// If total height is 0, the initial check handles it.
// Print -1 as a fallback for unexpected scenarios.
printf("-1\n");
}
}
return 0;
}