Submission #1282367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282367		iamhereforfun	Teams (IOI15_teams)	C++20	0 / 100	57 ms	16060 KiB

teams

#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 500000;

class SegmentTree {
private:
    vector<int> tree;
    int n;
    void build_tree(int node, int l, int r, const vector<int>& arr) {
        if (l == r) {
            tree[node] = arr[l];
            return;
        }
        int mid = (l + r) / 2;
        build_tree(2 * node, l, mid, arr);
        build_tree(2 * node + 1, mid + 1, r, arr);
        tree[node] = min(tree[2 * node], tree[2 * node + 1]);
    }
    int query_tree(int node, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return 1e9;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        int left_val = query_tree(2 * node, l, mid, ql, qr);
        int right_val = query_tree(2 * node + 1, mid + 1, r, ql, qr);
        return min(left_val, right_val);
    }
public:
    void build(const vector<int>& arr, int l, int r) {
        n = r - l + 1;
        tree.resize(4 * n);
        build_tree(1, l, r, arr);
    }
    int query(int ql, int qr) {
        return query_tree(1, 1, n, ql, qr);
    }
};

vector<int> H;
SegmentTree segTree;

void init(int N, int A[], int B[]) {
    int n = N;
    vector<int> freq(n + 2, 0);
    for (int i = 0; i < n; i++) {
        int b = B[i];
        if (b > n) b = n;
        freq[b]++;
    }
    H.resize(n + 1);
    H[n] = freq[n];
    for (int x = n - 1; x >= 1; x--) {
        H[x] = H[x + 1] + freq[x];
    }
    segTree.build(H, 1, n);
}

int can(int M, int K[]) {
    vector<int> req(K, K + M);
    sort(req.begin(), req.end());
    long long total = 0;
    for (int i = 0; i < M; i++) total += K[i];
    vector<long long> SS(M);
    for (int i = M - 1; i >= 0; i--) {
        SS[i] = total;
        total -= K[i];
    }
    for (int i = 0; i < M; i++) {
        int L = (i == 0) ? 1 : req[i - 1] + 1;
        int R = req[i];
        if (L > R) continue;
        int minH = segTree.query(L, R);
        if (minH < SS[i]) {
            return 0;
        }
    }
    return 1;
}

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