結果
| 問題 |
No.2220 Range Insert & Point Mex
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:08:26 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,329 bytes |
| コンパイル時間 | 2,533 ms |
| コンパイル使用メモリ | 95,512 KB |
| 実行使用メモリ | 8,368 KB |
| 最終ジャッジ日時 | 2025-05-14 13:10:13 |
| 合計ジャッジ時間 | 6,201 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 20 TLE * 1 -- * 15 |
ソースコード
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <vector> // Ensure vector is included
using namespace std;
// Define struct for intervals, holding start (l) and end (r) points.
struct Interval {
long long l, r;
};
/**
* @brief Computes the union of a list of intervals.
*
* Given a vector of intervals, this function returns a new vector containing
* the disjoint intervals that represent the union of the input intervals.
* It sorts the intervals by start point and merges overlapping or adjacent intervals.
*
* @param intervals A vector of Interval structs. Note: This vector will be modified (sorted).
* @return A vector of disjoint Interval structs representing the union.
*/
vector<Interval> union_intervals(vector<Interval>& intervals) {
// If the input vector is empty, the union is empty.
if (intervals.empty()) {
return {};
}
// Sort intervals based on their start points (l).
// This is necessary for the merging process.
sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
return a.l < b.l;
});
vector<Interval> result; // This vector will store the disjoint union intervals.
result.push_back(intervals[0]); // Initialize with the first interval.
// Iterate through the sorted intervals starting from the second one.
for (size_t i = 1; i < intervals.size(); ++i) {
// Check if the current interval overlaps with or is adjacent (touching) to the last interval in the result list.
// Two intervals [L1, R1] and [L2, R2] with L1 <= L2 overlap or touch if L2 <= R1 + 1.
if (intervals[i].l <= result.back().r + 1) {
// If they overlap or touch, merge them by updating the end point (r) of the last interval in result
// to be the maximum of its current end point and the current interval's end point.
result.back().r = max(result.back().r, intervals[i].r);
} else {
// If there is no overlap/adjacency, the current interval starts a new disjoint interval.
// Add it to the result list.
result.push_back(intervals[i]);
}
}
return result; // Return the vector of disjoint intervals.
}
/**
* @brief Checks if a point x is covered by any interval in a sorted list of disjoint intervals U_v.
*
* Uses binary search (via std::upper_bound) on the sorted interval list for efficiency.
*
* @param x The point to check.
* @param U_v A const reference to a vector of disjoint Interval structs, sorted by start point.
* @return true if x is covered by any interval in U_v, false otherwise.
*/
bool is_covered(long long x, const vector<Interval>& U_v) {
// If the interval list is empty, x cannot be covered.
if (U_v.empty()) {
return false;
}
// Use upper_bound to find the first interval whose start point is strictly greater than x.
// The custom comparator compares the probe value x (passed via probe.l in a temporary Interval)
// with the interval's start point (element.l).
auto it_upper = upper_bound(U_v.begin(), U_v.end(), Interval{x, -1}, [](const Interval& probe, const Interval& element) {
// Returns true if probe.l (representing x) is less than element.l
return probe.l < element.l;
});
// If upper_bound returns the beginning iterator, it means all intervals start after x.
// Thus, x cannot be covered by any interval starting at or before x.
if (it_upper == U_v.begin()) {
return false;
}
// The potential candidate interval that could cover x is the one immediately before it_upper.
// This interval is the *last* one in the sorted list whose start point is less than or equal to x.
auto candidate_it = it_upper - 1;
// Check if x falls within the start (l) and end (r) points of this candidate interval.
// If candidate_it->l <= x <= candidate_it->r, then x is covered.
if (candidate_it->l <= x && x <= candidate_it->r) {
return true; // x is covered.
}
// If x is not within the candidate interval, it is not covered by any interval in U_v.
return false;
}
// Global map to store the computed union of intervals for each relevant value a_i (0 <= a_i <= N).
// Key: value a_i. Value: vector of disjoint intervals representing the union U_{a_i}.
map<long long, vector<Interval>> U;
int main() {
// Optimize C++ standard input/output streams for speed.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of operations.
cin >> N;
// Temporary map to group operations by the value a_i before computing unions.
map<long long, vector<Interval>> ops_by_val;
for (int i = 0; i < N; ++i) {
long long l, r, a; // Read operation parameters: range [l, r], value a.
cin >> l >> r >> a;
// Optimization: Since Mex(S_x) <= N for any set S_x derived from N operations,
// we only need to track the presence of values a_i in the range [0, N].
// Operations adding values greater than N won't affect the Mex calculation if it's <= N.
if (a >= 0 && a <= N) {
ops_by_val[a].push_back({l, r}); // Store interval [l, r] associated with value a.
}
}
// Precompute the union of intervals U_v for each value v that appeared in the operations
// and is within the relevant range [0, N]. Store the results in the global map U.
for (auto& pair : ops_by_val) {
long long val = pair.first;
vector<Interval>& intervals = pair.second; // Get reference to avoid copying vector
U[val] = union_intervals(intervals); // Compute union and store it.
}
int Q; // Number of queries.
cin >> Q;
vector<long long> queries(Q); // Stores the query points x_k.
vector<int> query_indices(Q); // Stores the original indices (0 to Q-1) of the queries. Needed to output answers in correct order.
for (int i = 0; i < Q; ++i) {
cin >> queries[i];
query_indices[i] = i; // Initialize query indices 0, 1, ..., Q-1.
}
// Stores the final Mex answer for each query, indexed by original query index.
vector<int> final_ans(Q);
// Stores the indices of queries that are still active (i.e., their Mex has not yet been determined).
// Initially, all queries are active, corresponding to checking if Mex is 0.
vector<int> current_query_indices = query_indices;
// Iterate through potential Mex values v from 0 up to N.
// In each iteration v, we check for all active queries k if value v is present in S_{x_k}.
for (int v = 0; v <= N; ++v) {
// Optimization: If no queries are left active, we can stop the process early.
if (current_query_indices.empty()) {
break;
}
// Stores indices of queries that will remain active for checking potential Mex value v+1.
vector<int> next_query_indices;
// Check if value v exists in our precomputed map U. This tells us if v was ever added by any operation.
const vector<Interval>* ptr_U_v = nullptr; // Use a pointer to handle optional presence safely.
if (U.count(v)) {
ptr_U_v = &U.at(v); // If v exists, point to its list of union intervals.
}
// Process each currently active query index.
for (int original_idx : current_query_indices) {
long long x_k = queries[original_idx]; // Get the query coordinate x_k for this index.
bool covered = false;
// Check if x_k is covered by U_v only if U_v exists (i.e., v was added by some operation).
if (ptr_U_v != nullptr) {
covered = is_covered(x_k, *ptr_U_v); // Check if x_k falls within any interval in U_v.
}
if (covered) {
// If x_k is covered by U_v, it means v is present in S_{x_k}.
// The Mex must be greater than v. Keep this query active for the next iteration (check v+1).
next_query_indices.push_back(original_idx);
} else {
// If x_k is not covered by U_v, it means v is not present in S_{x_k}.
// Since we have checked values 0..v-1 in previous iterations and found them present (otherwise this query wouldn't be active),
// v is the smallest non-negative integer not present in S_{x_k}. Thus, v is the Mex.
final_ans[original_idx] = v; // Store the found Mex value for this query.
}
}
// Update the list of active queries for the next iteration using move semantics for efficiency.
current_query_indices = move(next_query_indices);
}
// After checking v = 0..N, any query still in current_query_indices must have 0..N all present in S_{x_k}.
// Based on the problem constraints (|S_x| <= N), this situation is impossible.
// A set with at most N elements cannot contain all N+1 integers {0, 1, ..., N}.
// Therefore, current_query_indices must be empty at this point.
// Print the computed Mex values for all queries in the original order.
for (int i = 0; i < Q; ++i) {
cout << final_ans[i] << "\n";
}
return 0; // Indicate successful execution.
}