#1083684 (C++17) No.1703 Much Matching

• 問題: 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;
}