結果
問題 | No.1703 Much Matching |
ユーザー |
![]() |
提出日時 | 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; }