제출 #1308184

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

teams

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

using namespace std;

// 定義最大值
const int MAXN = 500005;

// 線段樹節點
struct Node {
    int sum;
    int l, r;
} tree[MAXN * 25];

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

// 建樹
int build(int l, int r) {
    int u = ++node_cnt;
    tree[u].sum = 0;
    if (l == r) return u;
    int mid = (l + r) >> 1;
    tree[u].l = build(l, mid);
    tree[u].r = build(mid + 1, r);
    return u;
}

// 更新
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) >> 1;
    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;
}

// 查詢區間 [ql, qr] 的和
int query(int u, int v, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) return 0;
    if (ql <= l && r <= qr) return tree[u].sum - tree[v].sum;
    int mid = (l + r) >> 1;
    return query(tree[u].l, tree[v].l, l, mid, ql, qr) +
           query(tree[u].r, tree[v].r, mid + 1, r, ql, qr);
}

struct Student {
    int a, b;
} p[MAXN];

bool cmp(Student x, Student y) {
    return x.a < y.a;
}

// 初始化
void init(int N, int A[], int B[]) {
    N_val = N;
    for (int i = 0; i < N; i++) {
        p[i] = {A[i], B[i]};
    }
    sort(p, p + N, cmp);
    
    roots[0] = build(1, N);
    
    int cur = 0;
    for (int i = 1; i <= N; i++) {
        roots[i] = roots[i - 1];
        while (cur < N && p[cur].a == i) {
            roots[i] = update(roots[i], 1, N, p[cur].b);
            cur++;
        }
    }
}

// 獲取在 A 範圍 [1, x] 內，且 B 範圍 [y1, y2] 內的學生數
int count_range(int x, int y1, int y2) {
    if (y1 > y2) return 0;
    return query(roots[x], roots[0], 1, N_val, y1, y2);
}

// 驗證函數
int can(int M, int K[]) {
    sort(K, K + M);
    
    // Stack 元素: {k_value, b_limit, accumulated_usage}
    // k_value: 該層的隊伍人數限制
    // b_limit: 該層隊伍佔用的學生 B 值下界 (即該層隊伍使用的是 [b_limit, ???] 的學生)
    // 我們要維護一個階梯形狀，越上面的層，K 越大，b_limit 也應該越大 (Greedy: 大 K 用大 B)
    struct Element {
        int k;
        int b; // split point
        int val; // number of students used by this block plus previous blocks basically
    };
    
    vector<Element> st;
    
    for (int i = 0; i < M; i++) {
        int k = K[i];
        
        // 1. 如果當前 stack 頂部的 k 相同，可以簡單視為需求增加，
        // 但為了通用邏輯，我們每次都當作新的塊處理。
        
        // 我們需要刪掉 stack 中無法支撐 k 的部分
        // 也就是說，如果我們要在 k 處建立新塊，之前 stack 頂部如果 b < k，
        // 那些 b < k 的學生對當前 k 是無效的，但對 stack 內層是有效的。
        // 然而這裡我們不需要手動刪，因為查詢 count_range(k, ...) 自然會過濾掉 A > k 的情況?
        // 不，count_range 過濾的是 A。這裡 B 的過濾是透過 b_limit。
        // Greedy: 我們總是優先用 B 小的。
        
        while (!st.empty() && st.back().k >= k) {
            // 這種情況在 K 排序後一般不會發生 (除非有重複 K，或者邏輯反了)
            // 因為我們 K 是從小到大處理的。
            st.pop_back(); 
        }
        
        // 需要的人數
        int needed = k;
        
        // 開始回溯 Stack，找到合適的 b_limit
        while (!st.empty()) {
            Element top = st.back();
            // 計算從 top.b 到 N，在 A <= k 的條件下有多少人
            // 減去 之前層級已經佔用的人數 (top.val)
            // 實際上 top.val 存的是 "在 top.b 以上被 top 及其底下的層佔用的人數"
            
            // 計算：在 [top.b, N] 範圍內，滿足 A <= k 的人 - 滿足 A <= top.k 的人 (這些是新增的潛力股) ??
            // 不太對。標準公式是：
            // 我們想找一個位置 b_new > top.b，使得 [b_new, N] 內的可用學生數剛好滿足 (needed + stack_usage)
            
            int diff = count_range(k, top.b, N_val) - count_range(top.k, top.b, N_val);
            
            // 這裡的邏輯是：在 (top.k, k] 的 A 區間內，且 B >= top.b 的學生是 "額外多出來的資源"
            // 如果這些資源 + top 這一層剩餘的空間 < needed，那 top 層就撐不住了，要合併。
            
            // 正確的維護值：st[i].val = count_range(st[i].k, st[i].b, N_val) - (被 i 之前層用掉的) 

            int cnt = count_range(k, top.b, N_val);

            
            if (cnt - top.val < needed) {
                // 餘裕不足，需要吃掉這一層
                needed += top.val - count_range(top.k, top.b, N_val); // 回補這一層原本承諾的貢獻

                
                st.pop_back();
            } else {
                break;
            }
        }
        
        // 二分搜尋新的 b_start
        // 搜索範圍：如果 stack 為空，範圍是 [1, N+1]，否則 [st.back().b, N+1]
        // 我們要找最大的 b_new 使得 count(k, b_new, N) - (stack adjustments) >= needed
        
        int low = st.empty() ? 1 : st.back().b;
        int high = N_val + 1;
        int base_sub = st.empty() ? 0 : st.back().val; 
        int base_cnt = st.empty() ? 0 : count_range(st.back().k, st.back().b, N_val);
        
        
        int limit_val = needed + (base_cnt - base_sub);
        
      

        

        // 這樣就很清楚了。我們在 [low, N+1] 裡二分搜 b_new。
        // 使得 calc_diff(b_new) >= calc_diff(low) - needed 的最大 b_new (保留越多越好? 不，是剛好滿足)。
        // 實際上，因為 calc_diff 是隨 b 遞減的 (b 越大，count 越小)。
        // 所以 `calc_diff(low) - needed` 是一個目標值 Target。
        // 我們要找 b 使得 `calc_diff(b) >= Target` 的最大 b。
        // 如果連 calc_diff(low) < Target (即 needed < 0，不可能)，或者 calc_diff(N+1) > Target (不可能)。
        // 找到 b_new 後，如果 b_new > N，表示學生不夠 (需要吃到 N 以後)。
        
        int target = (count_range(k, low, N_val) - count_range(st.empty()?0:st.back().k, low, N_val) + (st.empty()?0:st.back().val)) - needed;
        
        int search_l = low, search_r = N_val + 1;
        int ans_b = -1;
        
        while(search_l <= search_r) {
            int mid = (search_l + search_r) >> 1;
            int val_mid = count_range(k, mid, N_val) - count_range(st.empty()?0:st.back().k, mid, N_val) + (st.empty()?0:st.back().val);
            if(val_mid >= target) {
                ans_b = mid;
                search_l = mid + 1; // 嘗試找更大的 b (保留更少的餘量，也就是吃掉更多? 不，val_mid >= target 代表餘量夠大)

            } else {
                search_r = mid - 1;
            }
        }
        
        if (ans_b == -1 || ans_b > N_val) {
            // 這裡有個 edge case，如果 ans_b 跑出去了，但實際上在 N+1 處 val 為 0。
            // 如果 target < 0，那即使吃到 N+1 也不夠。
             return 0;
        }
        
        // 找到了 b_new = ans_b
        // 新的 val 就是 target (或者 ans_b 處的實際 val)
        int new_val = count_range(k, ans_b, N_val) - count_range(st.empty()?0:st.back().k, ans_b, N_val) + (st.empty()?0:st.back().val);
        st.push_back({k, ans_b, new_val});
    }
    
    return 1;
}

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