結果
| 問題 |
No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:58:33 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 14,899 bytes |
| コンパイル時間 | 1,232 ms |
| コンパイル使用メモリ | 100,824 KB |
| 実行使用メモリ | 128,172 KB |
| 最終ジャッジ日時 | 2025-05-14 13:00:03 |
| 合計ジャッジ時間 | 15,238 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 1 WA * 9 |
ソースコード
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <tuple> // Required for std::tuple
using namespace std;
// Use unsigned long long for sums to handle potentially large values and ensure correct modulo arithmetic.
typedef unsigned long long ull;
// Define the modulus constant. The ULL suffix ensures it's treated as unsigned long long.
const ull MOD = 1000000000000000009ULL;
// Structure representing a node in the segment tree
struct Node {
// Stores the sum of thicknesses for each of the 5 teams (indexed 0-4) within the node's range.
ull SumThickness[5];
// Lazy propagation tag: 0 indicates no pending update, 1-5 indicates the ID of the team whose paint action is pending.
int lazy_team;
// The range of elementary interval indices [Lidx, Ridx] covered by this node.
int Lidx, Ridx;
// The actual coordinate range [P_left, P_right-1] covered by this node. P_right is the coordinate after the last index covered.
long long P_left, P_right;
};
vector<Node> tree; // Vector to store the segment tree nodes. Using 1-based indexing for nodes.
vector<long long> P; // Vector to store the sorted unique coordinates that define the elementary intervals.
map<long long, int> coord_to_idx; // Map to quickly find the index in P corresponding to a coordinate value.
/**
* @brief Applies a lazy tag update to a segment tree node.
* Represents the effect of team X painting the entire range covered by this node.
* Updates SumThickness based on the derived logic and sets the lazy tag.
* @param target_idx The index of the node in the tree vector to apply the update to.
* @param X The ID of the team (1-5) performing the paint action.
*/
void apply_lazy(int target_idx, int X) {
// If X is 0, it's not a valid team ID for painting, possibly indicates no update needed.
if (X == 0) return;
// Calculate the length of the coordinate range covered by this node.
long long node_len = tree[target_idx].P_right - tree[target_idx].P_left;
// Ensure length is not negative (shouldn't happen with correct build, but safety check).
if (node_len < 0) node_len = 0;
// Calculate the length modulo MOD. Use careful modulo arithmetic for potentially negative intermediate results (though node_len shouldn't be negative).
ull L_mod = (node_len % (long long)MOD + (long long)MOD) % MOD;
// Apply the update logic:
// SumThickness for team X increases by the range length (mod MOD).
// SumThickness for all other teams is reset to 0.
// Use X-1 for 0-based array indexing.
tree[target_idx].SumThickness[X - 1] = (tree[target_idx].SumThickness[X - 1] + L_mod) % MOD;
for (int Y = 1; Y <= 5; ++Y) {
if (Y != X) {
tree[target_idx].SumThickness[Y - 1] = 0;
}
}
// Set the lazy tag on this node to indicate that an update from team X is pending propagation.
tree[target_idx].lazy_team = X;
}
/**
* @brief Pushes the lazy tag from a parent node down to its children.
* Ensures children nodes are updated before they are accessed or further recursion.
* @param idx The index of the parent node in the tree vector.
*/
void push(int idx) {
// If there's no lazy tag or if it's a leaf node (no children to push to), do nothing.
if (tree[idx].lazy_team == 0 || tree[idx].Lidx == tree[idx].Ridx) {
// On a leaf node, any lazy tag is considered 'applied' as there are no children. Clear the tag.
if (tree[idx].Lidx == tree[idx].Ridx) tree[idx].lazy_team = 0;
return;
}
int lazy_X = tree[idx].lazy_team; // The team ID from the lazy tag.
// Apply the lazy update to the left child (index 2*idx).
apply_lazy(2 * idx, lazy_X);
// Apply the lazy update to the right child (index 2*idx+1).
apply_lazy(2 * idx + 1, lazy_X);
// After pushing the tag down, clear the lazy tag on the current node.
tree[idx].lazy_team = 0;
}
/**
* @brief Combines the results (SumThickness) from children nodes into their parent node.
* Called after recursive calls in update/query to maintain correct aggregate values in parent nodes.
* @param idx The index of the parent node in the tree vector.
*/
void combine(int idx) {
// The parent's SumThickness for each team is the sum of its children's SumThickness, modulo MOD.
for (int i = 0; i < 5; ++i) {
tree[idx].SumThickness[i] = (tree[2 * idx].SumThickness[i] + tree[2 * idx + 1].SumThickness[i]) % MOD;
}
}
/**
* @brief Builds the segment tree recursively.
* Initializes nodes with their ranges and default values (0 thickness, no lazy tag).
* @param idx The current node index in the tree vector (1-based).
* @param L_idx The starting index of the elementary interval range covered by this node.
* @param R_idx The ending index of the elementary interval range covered by this node.
*/
void build(int idx, int L_idx, int R_idx) {
// Set node properties based on the interval range it covers.
tree[idx].Lidx = L_idx;
tree[idx].Ridx = R_idx;
tree[idx].P_left = P[L_idx]; // The starting coordinate of the range.
tree[idx].P_right = P[R_idx + 1]; // The coordinate marking the end of the range (+1). P has m+1 elements.
tree[idx].lazy_team = 0; // Initialize with no lazy tag.
// Initialize thickness sums for all teams to 0.
for (int i = 0; i < 5; ++i) {
tree[idx].SumThickness[i] = 0;
}
// Base case: If it's a leaf node (covers a single elementary interval), return.
if (L_idx == R_idx) {
return;
}
// Recursive step: Build left and right children.
int M_idx = L_idx + (R_idx - L_idx) / 2; // Calculate midpoint index.
build(2 * idx, L_idx, M_idx); // Build left child.
build(2 * idx + 1, M_idx + 1, R_idx); // Build right child.
// No need to call combine initially, as all sums start at 0.
}
/**
* @brief Updates the segment tree for a given range of elementary intervals due to a paint action by team_X.
* Uses lazy propagation for efficiency.
* @param idx The current node index in the tree vector.
* @param query_L_idx The starting index of the query range (elementary intervals).
* @param query_R_idx The ending index of the query range.
* @param team_X The ID of the team (1-5) performing the paint action.
*/
void update(int idx, int query_L_idx, int query_R_idx, int team_X) {
int L_idx = tree[idx].Lidx; // Node's starting interval index.
int R_idx = tree[idx].Ridx; // Node's ending interval index.
// If the query range is completely outside the node's range, do nothing.
if (query_R_idx < L_idx || R_idx < query_L_idx) {
return;
}
// If the node's range is fully contained within the query range:
if (query_L_idx <= L_idx && R_idx <= query_R_idx) {
// Apply the lazy update to this node. This handles the update for the entire range covered by this node.
apply_lazy(idx, team_X);
return; // Stop recursion down this path.
}
// If the node's range partially overlaps the query range:
// First, push any existing lazy tag down to children. This ensures their state is current before further updates.
push(idx);
// Recursively call update on children. M_idx calculation is implicit in child indexing.
update(2 * idx, query_L_idx, query_R_idx, team_X); // Update left child.
update(2 * idx + 1, query_L_idx, query_R_idx, team_X); // Update right child.
// After children are updated, update the current node's state by combining their results.
combine(idx);
}
/**
* @brief Queries the segment tree for the sum of thicknesses for all teams within a given range of elementary intervals.
* @param idx The current node index in the tree vector.
* @param query_L_idx The starting index of the query range (elementary intervals).
* @param query_R_idx The ending index of the query range.
* @return A vector<ull> containing the sum of thicknesses for each of the 5 teams in the queried range.
*/
vector<ull> query(int idx, int query_L_idx, int query_R_idx) {
int L_idx = tree[idx].Lidx; // Node's starting interval index.
int R_idx = tree[idx].Ridx; // Node's ending interval index.
vector<ull> result(5, 0); // Initialize result vector with 0s for all 5 teams.
// If the query range is completely outside the node's range, return all zeros.
if (query_R_idx < L_idx || R_idx < query_L_idx) {
return result;
}
// If the node's range is fully contained within the query range:
if (query_L_idx <= L_idx && R_idx <= query_R_idx) {
// Return the sums stored in this node.
for(int i=0; i<5; ++i) result[i] = tree[idx].SumThickness[i];
return result;
}
// If the node's range partially overlaps the query range:
// Push any existing lazy tag down to ensure children's states are accurate before querying them.
push(idx);
// Recursively query children and combine their results.
vector<ull> left_sums = query(2 * idx, query_L_idx, query_R_idx); // Query left child.
vector<ull> right_sums = query(2 * idx + 1, query_L_idx, query_R_idx); // Query right child.
// Combine the sums from children, applying modulo arithmetic.
for (int i = 0; i < 5; ++i) {
result[i] = (left_sums[i] + right_sums[i]) % MOD;
}
return result; // Return the combined sums.
}
int main() {
// Faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long N; // Length of the array. Can be very large.
int Q; // Number of events (paint actions or bonus chances).
cin >> N >> Q;
// Use a set to collect unique coordinates. It automatically handles duplicates and sorting.
set<long long> coords;
coords.insert(0); // Always include the start coordinate 0.
coords.insert(N); // Always include coordinate N (represents the point after the last index N-1).
// Store events details (type, range) to process after coordinate compression and tree building.
vector<tuple<int, long long, long long>> events(Q);
for (int k = 0; k < Q; ++k) {
int x; // Event type: 0 for bonus, 1-5 for team paint.
long long l, r; // Range [l, r] for the event.
cin >> x >> l >> r;
events[k] = make_tuple(x, l, r);
// Add relevant coordinates l and r+1 to the set. These define the boundaries of elementary intervals.
// Check bounds to ensure coordinates are within [0, N].
if (l >= 0 && l <= N) coords.insert(l);
if (r + 1 >= 0 && r + 1 <= N) coords.insert(r + 1);
}
// Populate vector P with sorted unique coordinates from the set.
for(long long c : coords) {
P.push_back(c);
}
// Create a map from coordinate value to its index in P for quick lookups.
for (int i = 0; i < P.size(); ++i) {
coord_to_idx[P[i]] = i;
}
// Calculate the number of elementary intervals (m = number of unique coordinates - 1).
int m = P.size() - 1;
// Handle edge case: If N=0 or no operations result in intervals (m <= 0).
if (m <= 0) {
cout << "0 0 0 0 0" << endl; // Print all zeros and exit.
return 0;
}
// Allocate memory for the segment tree. Size 4*m is a safe upper bound for a binary tree based on m leaves. Add a small buffer for safety.
tree.resize(4 * m + 4);
// Build the segment tree structure over the elementary interval indices [0, m-1].
build(1, 0, m - 1); // Use 1-based indexing for segment tree nodes.
// Initialize bonus points for each team to 0.
vector<ull> BonusPoints(5, 0);
// Process each event chronologically.
for (int k = 0; k < Q; ++k) {
int x = get<0>(events[k]); // Event type.
long long l = get<1>(events[k]); // Left endpoint of range.
long long r = get<2>(events[k]); // Right endpoint of range.
// Ensure the range [l, r] is valid within the array bounds [0, N-1].
// Clamp coordinates defensively, though input constraints should guarantee validity (0 <= l <= r < N).
l = max(0LL, l);
r = min(N - 1, r);
// If after clamping l > r, the interval is empty, skip.
if (l > r) continue;
// Map the coordinate range [l, r] to the corresponding range of elementary interval indices [l_idx, r_idx].
int l_idx = coord_to_idx[l]; // Find index for coordinate l.
// Find index for coordinate r+1. Map lookup is safe because we added r+1 to coords set earlier.
int r_idx_plus_1 = coord_to_idx[r + 1];
int r_idx = r_idx_plus_1 - 1; // The index of the last elementary interval involved in the range [l, r].
// If the calculated index range is invalid (e.g., l_idx > r_idx), skip this event.
if (l_idx > r_idx) continue;
if (x == 0) { // Bonus chance event
// Query the segment tree for sums of thicknesses in the specified range [l_idx, r_idx].
vector<ull> sums = query(1, l_idx, r_idx);
ull max_sum = 0; // Find the maximum sum among all teams.
for (int i = 0; i < 5; ++i) {
if (sums[i] > max_sum) {
max_sum = sums[i];
}
}
// If the maximum sum is 0, no bonus points awarded.
if (max_sum == 0) continue;
int max_count = 0; // Count teams achieving the maximum sum.
int winner_team_idx = -1; // Store index (0-4) of potential winning team.
for (int i = 0; i < 5; ++i) {
if (sums[i] == max_sum) {
max_count++;
winner_team_idx = i;
}
}
// If exactly one team achieved the maximum sum, award bonus points (max_sum) to that team.
if (max_count == 1) {
BonusPoints[winner_team_idx] = (BonusPoints[winner_team_idx] + max_sum) % MOD;
}
} else { // Painting action event by team x (where x is 1-5).
// Update the segment tree for the specified range [l_idx, r_idx] and team x.
update(1, l_idx, r_idx, x);
}
}
// After processing all events, query the total thickness sums for the entire array range [0, N-1].
// This corresponds to querying the full range of elementary intervals [0, m-1].
vector<ull> final_thickness_sums = query(1, 0, m - 1);
// Calculate and print the final score for each team (A, B, C, D, E).
for (int i = 0; i < 5; ++i) {
// Final score = (Total Thickness Sum + Total Accumulated Bonus Points) % MOD.
ull final_score = (final_thickness_sums[i] + BonusPoints[i]) % MOD;
cout << final_score << (i == 4 ? "" : " "); // Print score with space separator, no space after the last score.
}
cout << endl; // Print newline at the end.
return 0; // Indicate successful execution.
}