제출 #1309033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309033		orzorzorz	팀들 (IOI15_teams)	C++20	0 / 100	361 ms	144028 KiB

teams

#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 500005;

// Persistent Segment Tree
struct Node {
    int l, r;
    int sum;
} tree[MAXN * 25]; // Sufficient size for N log N updates

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

// Standard Persistent Segment Tree Update
void update(int &node, int prev_node, int l, int r, int idx) {
    node = ++cnt_nodes;
    tree[node] = tree[prev_node];
    tree[node].sum++;
    if (l == r) return;
    int mid = (l + r) / 2;
    if (idx <= mid) update(tree[node].l, tree[prev_node].l, l, mid, idx);
    else update(tree[node].r, tree[prev_node].r, mid + 1, r, idx);
}

// Range Sum Query
int query(int node, int l, int r, int ql, int qr) {
    if (ql > qr || !node) return 0;
    if (ql <= l && r <= qr) return tree[node].sum;
    int mid = (l + r) / 2;
    int res = 0;
    if (ql <= mid) res += query(tree[node].l, l, mid, ql, qr);
    if (qr > mid) res += query(tree[node].r, mid + 1, r, ql, qr);
    return res;
}

// Helper to count students with A in (a_min, a_max] and B in [b_min, N]
int get_count(int a_min, int a_max, int b_min) {
    if (a_min >= a_max) return 0;
    if (b_min > N_val) return 0;
    return query(root[a_max], 1, N_val, b_min, N_val) - query(root[a_min], 1, N_val, b_min, N_val);
}

void init(int N, int A[], int B[]) {
    N_val = N;
    cnt_nodes = 0;
    
    // Organize students by their minimum team size A[i]
    vector<vector<int>> by_A(N + 1);
    for (int i = 0; i < N; i++) {
        by_A[A[i]].push_back(B[i]);
    }
    
    // Build Persistent Segment Tree
    // root[i] stores version containing all students with A <= i
    root[0] = 0;
    for (int i = 1; i <= N; i++) {
        root[i] = root[i-1];
        for (int b_val : by_A[i]) {
            int new_root;
            update(new_root, root[i], 1, N, b_val);
            root[i] = new_root;
        }
    }
}

struct Project {
    int k, m;
};

// Stack element to maintain the lower envelope of feasibility
struct Element {
    int p_idx;      // Index in the unique projects array
    long long dp_val; // The 'slack' available after satisfying projects up to p_idx
};

int can(int M, int K[]) {
    // 1. Sort and group projects by size
    vector<int> rawK;
    for(int i = 0; i < M; ++i) rawK.push_back(K[i]);
    sort(rawK.begin(), rawK.end());
    
    vector<Project> projects;
    for(int i = 0; i < M; ) {
        int j = i;
        int sum_m = 0;
        while(j < M && rawK[j] == rawK[i]) {
            sum_m += rawK[i]; // Demand is sum of sizes
            j++;
        }
        projects.push_back({rawK[i], sum_m});
        i = j;
    }
    
    // 2. Process projects using Stack
    vector<Element> st;
    
    for (int i = 0; i < projects.size(); ++i) {
        int k_curr = projects[i].k;
        long long m_curr = projects[i].m;
        
        // Check if current constraint K dominates previous stack elements
        while (!st.empty()) {
            int top_idx = st.back().p_idx;
            long long top_dp = st.back().dp_val;
            
            int prev_idx = (st.size() > 1) ? st[st.size() - 2].p_idx : -1;
            int k_prev = (prev_idx == -1) ? 0 : projects[prev_idx].k;
            int k_top = projects[top_idx].k;
            
            // Calculate students in A range (k_prev, k_top] that are valid for k_top
            // but become INVALID for k_curr because their B is too small ( < k_curr )
            int lost = get_count(k_prev, k_top, k_top) - get_count(k_prev, k_top, k_curr);
            
            long long prev_dp = (st.size() > 1) ? st[st.size() - 2].dp_val : 0;
            
            // If the slack at top (projected to new constraint) is worse than or equal to 
            // the slack at prev, then 'top' is dominated and we merge it.
            if (top_dp - lost <= prev_dp) {
                st.pop_back();
            } else {
                break;
            }
        }
        
        // 3. Calculate new slack for current project
        int prev_idx = st.empty() ? -1 : st.back().p_idx;
        int k_prev = (prev_idx == -1) ? 0 : projects[prev_idx].k;
        long long prev_dp = st.empty() ? 0 : st.back().dp_val;
        
        // New slack = Slack from previous + Newly available students - Demand
        // Newly available = Students with A in (k_prev, k_curr] and B >= k_curr
        int gained = get_count(k_prev, k_curr, k_curr);
        long long new_dp = prev_dp + gained - m_curr;
        
        if (new_dp < 0) return 0; // Impossible to satisfy
        
        st.push_back({i, new_dp});
    }
    
    return 1;
}

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