Submission #1306073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306073		orzorzorz	Teams (IOI15_teams)	C++20	0 / 100	436 ms	141788 KiB

teams

/**
 * IOI 2015 - Teams
 * Solution using Persistent Segment Tree and Monotonic Stack
 * Time Complexity: O((N + sum(M)) * log N)
 * Space Complexity: O(N log N)
 */

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

const int MAXN = 500005;
const int INF = 1e9 + 7;

struct Node {
    int sum;
    int l, r;
} tree[MAXN * 25];

int root[MAXN];
int node_cnt = 0;
int N_val;

// Build an empty tree
int build(int l, int r) {
    int u = ++node_cnt;
    tree[u].sum = 0;
    if (l == r) return u;
    int mid = (l + r) / 2;
    tree[u].l = build(l, mid);
    tree[u].r = build(mid + 1, r);
    return u;
}

// Update the tree persistently
int update(int prev, int l, int r, int pos) {
    int u = ++node_cnt;
    tree[u] = tree[prev];
    tree[u].sum++;
    if (l == r) return u;
    int mid = (l + r) / 2;
    if (pos <= mid)
        tree[u].l = update(tree[prev].l, l, mid, pos);
    else
        tree[u].r = update(tree[prev].r, mid + 1, r, pos);
    return u;
}

// Query sum in range [ql, qr]
int query(int u, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) return 0;
    if (ql <= l && r <= qr) return tree[u].sum;
    int mid = (l + r) / 2;
    return query(tree[u].l, l, mid, ql, qr) + query(tree[u].r, mid + 1, r, ql, qr);
}

// Function to find the smallest x such that:
// Count(A <= x, y_low <= B <= y_high) >= val
// This binary searches over the versions of the persistent tree (roots).
int find_split(int val, int y_low, int y_high) {
    int l = 1, r = N_val;
    int ans = N_val + 1;
    
    while (l <= r) {
        int mid = (l + r) / 2;
        if (query(root[mid], 1, N_val, y_low, y_high) >= val) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

void init(int N, int A[], int B[]) {
    N_val = N;
    // Prepare students sorted by A
    vector<pair<int, int>> students(N);
    for (int i = 0; i < N; i++) {
        students[i] = {A[i], B[i]};
    }
    sort(students.begin(), students.end());

    // Build initial empty tree
    root[0] = build(1, N);

    // Build persistent versions based on A
    // root[x] contains all students with A[i] <= x
    int ptr = 0;
    for (int x = 1; x <= N; x++) {
        root[x] = root[x - 1];
        while (ptr < N && students[ptr].first == x) {
            root[x] = update(root[x], 1, N, students[ptr].second);
            ptr++;
        }
    }
}

int can(int M, int K[]) {
    // Sort the current query requirements
    vector<int> k_sorted(M);
    for (int i = 0; i < M; i++) k_sorted[i] = K[i];
    sort(k_sorted.begin(), k_sorted.end());

    // Monotonic Stack
    // Stores pair {index_in_k_sorted, split_value_x}
    // We use a custom struct or pair
    struct Element {
        int idx;
        int split_val;
    };
    
    vector<Element> st;
    // Dummy element for the base case (index -1)
    // S[-1] is effectively 0. K[-1+1] = K[0].
    st.push_back({-1, -INF}); 

    // Used to track sums of team sizes
    // We compute prefix sums on the fly or just use current logic
    // Using simple accumulation might overflow int if M is large, 
    // but Constraints say sum of M is small. However, K[i] can be N.
    // Sum can exceed 2^31. Use long long.
    // But inside the logic, we check differences.
    // Let's store prefix sums array.
    vector<long long> S(M + 1, 0); 
    // S[i] = sum(K[0]...K[i]). 
    // We map index -1 to a virtual S[-1] = 0.
    // To simplify, let's just use S[i] as sum of K[0]...K[i].
    
    long long current_S = 0;

    for (int i = 0; i < M; i++) {
        current_S += k_sorted[i];
        S[i] = current_S;

        // 1. Check validity using the best constraint from the stack
        // We need the stack element whose split_val <= k_sorted[i]
        // Since split_val is monotonic in the stack, we can remove elements from the bottom 
        // if we used a deque, but vector is fine with an index pointer, 
        // or just binary search / verify the top isn't the only way.
        // Actually, since we only add elements with HIGHER split_val, 
        // and we query with increasing k_sorted[i], we effectively "move right".
        // BUT, we are building the stack as we go. The `i` is the query point.
        // The stack contains `j < i`.
        // We just need to remove elements from the BACK if they are dominated by new `i`.
        // But for querying the validity of `i` itself, we look at the stack constructed so far.
        // The active constraint is the one with highest split_val <= k_sorted[i].
        // Since we cleaned the stack in previous steps, and k is increasing,
        // we might need to search. However, usually the stack top or near top is relevant?
        // No, the stack stores history. We need binary search on the stack.
        
        // Wait, the standard "Monotonic Stack" for this problem implies we pop from the back 
        // when adding `i`, but for checking `i`, we use the stack.
        // Let's implement binary search on the stack to find the active segment.
        
        int l = 0, r = st.size() - 1;
        int best_idx = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (st[mid].split_val <= k_sorted[i]) {
                best_idx = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        
        int j = st[best_idx].idx;
        long long S_j = (j == -1) ? 0 : S[j];
        // The minimal B requirement for group j+1 ... i is K[j+1]
        // Range of B: [K[j+1], N]
        // Count available students with A <= K[i] and B >= K[j+1]
        int count = query(root[k_sorted[i]], 1, N_val, k_sorted[j + 1], N_val);
        
        if (count < current_S - S_j) {
            return 0;
        }

        // 2. Add current i to stack
        // We need to determine where `i` dominates the current stack top.
        while (true) {
            int top_idx = st.back().idx;
            // Compare i with top_idx
            // We want to find smallest x such that:
            // Count(A <= x, B in [K[top_idx+1], K[i+1] - 1]) >= S[i] - S[top_idx]
            
            // Range B:
            int y_low = k_sorted[top_idx + 1];
            int y_high = k_sorted[i + 1] - 1; 
            // Note: if i was the last element, we don't add it to stack? 
            // The problem loops 0..M-1. We need to add i to stack if i < M-1.
            // Because j serves as the "start of a range" for FUTURE queries.
            // If i is the last element, it won't be a 'j' for anyone.
            if (i == M - 1) break;

            long long diff = S[i] - ((top_idx == -1) ? 0 : S[top_idx]);
            
            // If the range is invalid (y_low > y_high), it means K[top+1] > K[i+1]-1.
            // Since K is sorted, K[top+1] <= K[i+1].
            // If K[top+1] == K[i+1], range is empty, count is 0.
            // If diff > 0, split becomes INF.
            
            int split = find_split((int)diff, y_low, y_high);
            
            if (split <= st.back().split_val) {
                st.pop_back();
                if (st.empty()) {
                    // Should not happen given dummy -1, but for safety
                    st.push_back({i, split});
                    break;
                }
            } else {
                st.push_back({i, split});
                break;
            }
        }
    }

    return 1;
}

// Helper for the local testing environment or grader
// This part is conditional based on whether main() is provided by grader
#ifdef LOCAL_TEST
int main() {
    int N;
    if (!(cin >> N)) return 0;
    vector<int> A(N), B(N);
    for(int i=0; i<N; i++) cin >> A[i] >> B[i];
    init(N, A.data(), B.data());
    int Q;
    cin >> Q;
    while(Q--) {
        int M;
        cin >> M;
        vector<int> K(M);
        for(int i=0; i<M; i++) cin >> K[i];
        cout << can(M, K.data()) << endl;
    }
    return 0;
}
#endif

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23