結果
| 問題 |
No.1703 Much Matching
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:55:53 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 408 ms / 2,000 ms |
| コード長 | 7,703 bytes |
| コンパイル時間 | 719 ms |
| コンパイル使用メモリ | 86,076 KB |
| 実行使用メモリ | 11,000 KB |
| 最終ジャッジ日時 | 2025-05-14 12:57:28 |
| 合計ジャッジ時間 | 4,494 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Use 0 as the minimum possible value / identity element for the max operation.
// Since DP values represent chain lengths, they are always >= 1. So 0 works as minimum.
const int MIN_VAL = 0;
// Define the structure for a node in the segment tree.
// Each node stores the maximum value in the range it represents.
struct SegTreeNode {
int max_val;
};
// Global vector to store the segment tree nodes.
vector<SegTreeNode> tree;
// Stores the size of the range [1, M] covered by the segment tree.
int N_seg;
/**
* @brief Initializes the segment tree structure.
* @param M_val The maximum possible woman ID (size of the range [1, M]).
* The tree will cover the range [1, M_val].
*/
void build(int M_val) {
N_seg = M_val;
// Allocate sufficient space for the segment tree array.
// 4*N_seg is a safe upper bound for the number of nodes needed.
tree.assign(4 * N_seg + 4, {MIN_VAL}); // Initialize all max values to MIN_VAL (0)
}
/**
* @brief Updates the segment tree at a specific index.
* @param node The current node index in the tree array (1-based).
* @param start The start of the range represented by the current node.
* @param end The end of the range represented by the current node.
* @param idx The index (woman ID) to update.
* @param val The new DP value computed for the pair ending with woman ID `idx`.
* The update logic ensures that the value stored for index `idx` becomes max(current_value, val).
*/
void update(int node, int start, int end, int idx, int val) {
// Base case: If we reach the leaf node corresponding to index `idx`.
if (start == end) {
tree[node].max_val = max(tree[node].max_val, val);
return;
}
// Recursive step: Determine whether to go left or right based on `idx`.
int mid = start + (end - start) / 2;
if (idx <= mid) { // Check if index `idx` is within the left child's range [start, mid].
update(2 * node, start, mid, idx, val); // Recurse on the left child.
} else { // Index `idx` must be in the right child's range [mid+1, end].
update(2 * node + 1, mid + 1, end, idx, val); // Recurse on the right child.
}
// After updating a child, update the current node's value.
// It should be the maximum of its children's maximum values.
tree[node].max_val = max(tree[2 * node].max_val, tree[2 * node + 1].max_val);
}
/**
* @brief Queries the segment tree for the maximum value in a given range [L, R].
* @param node The current node index in the tree array (1-based).
* @param start The start of the range represented by the current node.
* @param end The end of the range represented by the current node.
* @param L The start of the query range.
* @param R The end of the query range.
* @return The maximum value found in the intersection of the node's range [start, end] and the query range [L, R].
*/
int query(int node, int start, int end, int L, int R) {
// Case 1: The query range [L, R] is completely outside the node's range [start, end].
// Also correctly handles empty query ranges where L > R (e.g., querying [1, 0]).
if (R < start || end < L || L > R) {
return MIN_VAL; // Return the identity element for max operation.
}
// Case 2: The node's range [start, end] is completely inside the query range [L, R].
if (L <= start && end <= R) {
return tree[node].max_val; // Return the precomputed max value stored in this node.
}
// Case 3: The node's range partially overlaps with the query range.
// Recursively query the left and right children and return the maximum of their results.
int mid = start + (end - start) / 2;
int p1 = query(2 * node, start, mid, L, R); // Query the left child.
int p2 = query(2 * node + 1, mid + 1, end, L, R); // Query the right child.
return max(p1, p2); // Return the overall maximum from the relevant parts of children.
}
int main() {
// Use fast I/O operations.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, Q; // N: number of men, M: number of women, Q: number of possible pairs
cin >> N >> M >> Q;
// Read the Q possible pairs into a vector of pairs.
vector<pair<int, int>> P(Q);
for (int i = 0; i < Q; ++i) {
cin >> P[i].first >> P[i].second; // P[i].first: man ID, P[i].second: woman ID
}
// If there are no possible pairs (Q=0), the maximum chain length is 0.
if (Q == 0) {
cout << 0 << endl;
return 0;
}
// Sort the pairs. The primary sort key is the man ID (P[i].first),
// and the secondary sort key is the woman ID (P[i].second).
sort(P.begin(), P.end());
// Constraints state M >= 1. If M could be 0, we would need to handle that case.
// Check if M=0 just in case, although problem constraints say M >= 1.
if (M == 0) {
cout << 0 << endl;
return 0;
}
// Build the segment tree. It will cover the range of woman IDs [1, M].
build(M);
int max_len = 0; // Stores the maximum length of a valid chain found so far.
// Temporary storage for updates. Stores pairs (woman_id, dp_value) for the current man ID being processed.
// Updates are applied in batches after processing all pairs for a specific man.
vector<pair<int, int>> updates;
// Iterate through the sorted pairs.
for (int i = 0; i < Q; ++i) {
int current_man = P[i].first;
int current_woman = P[i].second;
// Check if the current pair belongs to a different man than the previous pair.
// This condition is relevant only for i > 0.
if (i > 0 && current_man != P[i-1].first) {
// If it's a new man, first apply all the updates collected for the previous man ID.
// This ensures that DP values computed for man X only become available for men X' > X.
for (const auto& upd : updates) {
// Update the segment tree at index `upd.first` (woman ID) with the computed DP value `upd.second`.
// The segment tree uses 1-based indexing corresponding to woman IDs.
update(1, 1, M, upd.first, upd.second);
}
// Clear the updates list to start collecting updates for the new man ID.
updates.clear();
}
// Query the segment tree for the maximum DP value among pairs (x, y) such that x < current_man and y < current_woman.
// The query range for woman IDs is [1, current_woman - 1].
// query(root_node=1, tree_range_start=1, tree_range_end=M, query_range_start=1, query_range_end=current_woman - 1)
int V = query(1, 1, M, 1, current_woman - 1);
// Calculate the DP value (length of the longest chain ending with the current pair).
// It's 1 (for the current pair) + the max length of a chain ending before it satisfying conditions.
int current_dp = 1 + V;
// Store the computed DP value along with the woman ID in the temporary updates list.
// This update will be applied to the segment tree later.
updates.push_back({current_woman, current_dp});
// Update the overall maximum length found so far.
max_len = max(max_len, current_dp);
}
// After iterating through all pairs, there might be pending updates from the last group of pairs
// (belonging to the last man ID processed). Apply these final updates.
for (const auto& upd : updates) {
update(1, 1, M, upd.first, upd.second);
}
// Output the final maximum length found.
cout << max_len << endl;
return 0;
}