Submission #1308061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308061		orzorzorz	Teams (IOI15_teams)	C++20	0 / 100	1509 ms	155856 KiB

teams

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

using namespace std;

// Memory pool for Persistent Segment Tree
// N up to 500,000. logN ~ 19. 2*N*19 nodes approx. 20M is safe.
const int MAX_NODES = 20000000;
const int MAX_N = 500005;

struct Node {
    int sum;
    int left, right;
} tree[MAX_NODES];

int root[MAX_N];
int pst_cnt = 0;
int N_val;

// Build an initial empty segment tree
int build(int l, int r) {
    int id = ++pst_cnt;
    tree[id].sum = 0;
    if (l == r) {
        tree[id].left = tree[id].right = 0;
        return id;
    }
    int mid = (l + r) / 2;
    tree[id].left = build(l, mid);
    tree[id].right = build(mid + 1, r);
    return id;
}

// Create a new version of the tree with value at pos incremented
int update(int prev_node, int l, int r, int pos) {
    int id = ++pst_cnt;
    tree[id] = tree[prev_node]; // Copy data from previous version
    tree[id].sum++;
    if (l == r) return id;
    int mid = (l + r) / 2;
    if (pos <= mid) {
        tree[id].left = update(tree[prev_node].left, l, mid, pos);
    } else {
        tree[id].right = update(tree[prev_node].right, mid + 1, r, pos);
    }
    return id;
}

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

// Initialization function required by the problem
void init(int N, int A[], int B[]) {
    N_val = N;
    pst_cnt = 0;
    
    // Group students by their minimum team size A[i]
    // Indices are 1-based, array is 0-based
    vector<vector<int>> students_by_A(N + 1);
    for (int i = 0; i < N; ++i) {
        students_by_A[A[i]].push_back(B[i]);
    }

    // Build base tree (version 0)
    root[0] = build(1, N);
    
    // Build persistent versions. root[i] contains all students with A <= i.
    for (int i = 1; i <= N; ++i) {
        root[i] = root[i-1];
        for (int b_val : students_by_A[i]) {
            root[i] = update(root[i], 1, N, b_val);
        }
    }
}

// Function to check if valid assignment is possible for the day
int can(int M, int K[]) {
    // Sort project requirements
    vector<int> sorted_K(M);
    for(int i = 0; i < M; ++i) sorted_K[i] = K[i];
    sort(sorted_K.begin(), sorted_K.end());

    struct Element {
        int k_val; // The project size constraint A <= k_val
        int y_val; // The B-value up to which students are used
    };
    
    // Stack maintains the "boundary" of used students.
    // {0, N_val} acts as a sentinel representing the entire available space initially.
    vector<Element> st;
    st.push_back({0, N_val}); 

    for (int k : sorted_K) {
        // Since k increases, any previously used block that ended before k (y_val < k)
        // is no longer relevant as a restriction because we only care about B >= k.
        while (st.size() > 1 && st.back().y_val < k) {
            st.pop_back();
        }

        int demand = k;
        int last_start = k; // We start looking for students with B >= k
        
        // Try to satisfy 'demand' by merging stack segments or filling gaps
        while (true) {
            if (st.empty()) return 0; // Should not happen due to sentinel, unless N < k (impossible)
            
            Element top = st.back();
            
            // We search in the range [last_start, top.y_val].
            // If last_start > top.y_val, this segment is fully consumed/skipped.
            if (last_start > top.y_val) {
                 st.pop_back();
                 continue;
            }
            
            // Calculate number of available students in [last_start, top.y_val] with A <= k.
            // "Available" means: Total in range (A <= k) MINUS Already used (A <= top.k_val).
            // root[top.k_val] represents the usage profile of the stack top.
            int added_capacity = query(root[k], 1, N_val, last_start, top.y_val) 
                               - query(root[top.k_val], 1, N_val, last_start, top.y_val);
                               
            if (added_capacity >= demand) {
                // We can satisfy the remaining demand within this segment.
                // Binary search to find the smallest Y such that we take exactly 'demand' students.
                int low = last_start, high = top.y_val;
                int ans = high;
                
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    int cap = query(root[k], 1, N_val, last_start, mid) 
                            - query(root[top.k_val], 1, N_val, last_start, mid);
                    if (cap >= demand) {
                        ans = mid;
                        high = mid - 1;
                    } else {
                        low = mid + 1;
                    }
                }
                
                // We found the new boundary Y = ans.
                // This project effectively consumes students up to ans.
                st.push_back({k, ans});
                break; // Done with this project
            } else {
                // Not enough students in this segment. Take all of them and continue.
                demand -= added_capacity;
                last_start = top.y_val + 1;
                st.pop_back(); // Remove this segment as we've "surpassed" it
                
                // Check if we exhausted everything including sentinel
                if (st.empty() && demand > 0) return 0;
            }
        }
    }
    
    return 1;
}

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