Submission #1308628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308628		orzorzorz	Teams (IOI15_teams)	C++20	0 / 100	1096 ms	379120 KiB

teams

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

using namespace std;

const int MAXN = 500005;

// --- Persistent Segment Tree ---
struct Node {
    int count;
    Node *left, *right;
    
    Node(int count, Node *left, Node *right) : count(count), left(left), right(right) {}
};

Node* null;
Node* roots[MAXN]; 

// Build an empty tree
Node* build(int l, int r) {
    if (l == r) return new Node(0, null, null);
    int mid = l + (r - l) / 2;
    return new Node(0, build(l, mid), build(mid + 1, r));
}

// Update the tree (Add 1 at position p)
Node* update(Node* node, int l, int r, int p) {
    if (l == r) return new Node(node->count + 1, null, null);
    int mid = l + (r - l) / 2;
    if (p <= mid) return new Node(node->count + 1, update(node->left, l, mid, p), node->right);
    else return new Node(node->count + 1, node->left, update(node->right, mid + 1, r, p));
}

// Standard Query: Count in range [ql, qr] for a specific version
int query(Node* node, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) return 0;
    if (ql <= l && r <= qr) return node->count;
    int mid = l + (r - l) / 2;
    return query(node->left, l, mid, ql, qr) + query(node->right, mid + 1, r, ql, qr);
}

// --- Critical Helper Function ---
// Find smallest index 'x' (in range of A-values) such that:
// Count of students with A <= x AND B in [yl, yr] >= k
int search_tree(Node* node_l, Node* node_r, int l, int r, int yl, int yr, int k) {
    // If total students in this full node range [yl, yr] < k, we can't find such x here
    // Note: This logic is slightly different. We are searching for 'x' (time/version),
    // but the tree is built on B-values. 
    // Actually, to search 'x' efficiently, we usually just Binary Search on the versions.
    // However, O(log^2 N) is acceptable. 
    // A strict O(log N) requires a different tree structure (Tree of B values, nodes store A).
    // But for IOI Teams, simple Binary Search on the answer 'x' is standard and passes.
    
    // We will implement Binary Search in the 'solve' function for clarity and safety.
    return 0; 
}

int N;
vector<int> adj[MAXN];

// Wrapper to count students with A <= x AND B in [y1, y2]
int count_students(int x, int y1, int y2) {
    if (y1 > y2) return 0;
    return query(roots[x], 1, N, y1, y2);
}

// Initial Setup
void init(int n, int A[], int B[]) {
    N = n;
    null = new Node(0, nullptr, nullptr);
    null->left = null->right = null;
    roots[0] = build(1, N);

    for (int i = 0; i < N; i++) {
        adj[A[i]].push_back(B[i]);
    }

    for (int i = 1; i <= N; i++) {
        roots[i] = roots[i-1];
        for (int b : adj[i]) {
            roots[i] = update(roots[i], 1, N, b);
        }
    }
}

// DP State
int dp[MAXN]; // Stores the "slack" (available - used)
int K_sorted[MAXN];

// Binary Search to find the split point between index i and j in the stack
// We want to find the coordinate 'x' where the transition from i equals transition from j
int find_split(int i, int j) {
    // We want smallest x such that:
    // count(x, K[i]+1, K[j]) >= dp[j] - dp[i]
    // where K[i] < K[j].
    
    int target = dp[j] - dp[i];
    int l = K_sorted[j], r = N + 1; // Range of possible A-values
    
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (count_students(mid, K_sorted[i] + 1, K_sorted[j]) >= target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

int can(int M, int K[]) {
    // 1. Sort Groups
    for(int i=0; i<M; i++) K_sorted[i] = K[i];
    sort(K_sorted, K_sorted + M);
    
    // 2. Setup Stack
    // Stack stores indices of K_sorted
    vector<int> st; 
    
    // Use a dummy base case
    // We treat index -1 as having K=0, dp=0
    // But to avoid negative indices, let's manually handle the first element logic
    // or just assume implicit base.
    
    // Let's use clean iteration.
    // DP definition: dp[i] = max students remaining after satisfying groups 0...i
    // dp[i] = min_{j < i} ( dp[j] + count(K[i], K[j]+1, K[i]) ) - K[i]
    
    // Re-mapped logic to match standard variables:
    // We actually just compute values on the fly.
    
    st.clear();
    // Dummy element representing K=0, dp=0
    // We can't push a real index, so we handle the first step separately 
    // or insert a dummy into K_sorted? 
    // Inserting dummy is safer.
    
    vector<int> k_real;
    k_real.push_back(0);
    for(int i=0; i<M; i++) k_real.push_back(K_sorted[i]);
    
    // Reset DP array (only need size M+1)
    // Note: In global scope, dp is size MAXN, but here we index by 0..M
    // We'll use a local vector or reuse the global one carefully.
    
    vector<int> local_dp(M + 1, 0); 
    st.push_back(0); // Index 0 is the dummy (K=0, dp=0)
    
    for (int i = 1; i <= M; i++) {
        int k = k_real[i];
        
        // Stack Maintenance
        while (st.size() > 1) {
            int j = st.back();          // Top
            int l = st[st.size() - 2];  // Second Top
            
            // Check if 'j' is redundant.
            // It is redundant if the split point between l and j is >= split point between j and i
            // Or simpler: find split point between l and j. If that split is > k, j is useless?
            // Correct Logic:
            // The split point is where the "influence" of l ends and j begins.
            // If that split point is to the right of 'k', then for current 'k', l is strictly better/same as j.
            
            int split = find_split(l, j); // Uses global K_sorted logic, need to adapt to k_real
            // Careful with variable mapping. Let's fix find_split to take direct K values or indices into k_real.
            
            // Inline Find Split for indices l and j in k_real:
            int target = local_dp[j] - local_dp[l];
            int low = k_real[j], high = N + 1;
            int split_pos = N + 1;
            while(low < high) {
                int mid = low + (high - low)/2;
                if (count_students(mid, k_real[l] + 1, k_real[j]) >= target) {
                    split_pos = mid;
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            
            if (split_pos <= k) {
                st.pop_back();
            } else {
                break;
            }
        }
        
        int j = st.back();
        // Calculate DP[i]
        // dp[i] = dp[j] + count(k, K[j]+1, k) - k
        int valid_cnt = count_students(k, k_real[j] + 1, k);
        local_dp[i] = local_dp[j] + valid_cnt - k;
        
        if (local_dp[i] < 0) return 0; // Impossible
        
        st.push_back(i);
    }

    return 1;
}

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