Submission #1309952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309952		jg86	Teams (IOI15_teams)	C++17	100 / 100	614 ms	130060 KiB

teams

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int l, r;
    int sum;
};

static int N;
static vector<int> roots;
static vector<Node> seg;
static size_t baseSizeAfterInit;

static inline int clone_node(int from) {
    seg.push_back(seg[from]);
    return (int)seg.size() - 1;
}

static int update_point(int node, int l, int r, int pos) {
    int n = clone_node(node);
    if (l == r) {
        seg[n].sum++;
        return n;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) seg[n].l = update_point(seg[n].l, l, mid, pos);
    else seg[n].r = update_point(seg[n].r, mid + 1, r, pos);
    seg[n].sum = seg[seg[n].l].sum + seg[seg[n].r].sum;
    return n;
}

static int query_diff(int pref, int used, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return seg[pref].sum - seg[used].sum;
    int mid = (l + r) >> 1;
    return query_diff(seg[pref].l, seg[used].l, l, mid, ql, qr) +
           query_diff(seg[pref].r, seg[used].r, mid + 1, r, ql, qr);
}

static int consume_suffix(int pref, int used, int l, int r, int start, int &need) {
    if (need == 0 || r < start) return used;

    if (l >= start) {
        int avail = seg[pref].sum - seg[used].sum;
        if (avail == 0) return used;
        if (avail <= need) {
            need -= avail;
            return pref;
        }
        if (l == r) {
            int n = clone_node(used);
            seg[n].sum += need;
            need = 0;
            return n;
        }
    }

    if (l == r) return used;

    int mid = (l + r) >> 1;
    int n = clone_node(used);

    if (start <= mid)
        seg[n].l = consume_suffix(seg[pref].l, seg[used].l, l, mid, start, need);
    else
        seg[n].l = seg[used].l;

    seg[n].r = consume_suffix(seg[pref].r, seg[used].r, mid + 1, r, start, need);
    seg[n].sum = seg[seg[n].l].sum + seg[seg[n].r].sum;
    return n;
}

void init(int N_, int A[], int B[]) {
    N = N_;

    vector<pair<int,int>> students;
    students.reserve(N);
    for (int i = 0; i < N; i++) students.push_back({A[i], B[i]});
    sort(students.begin(), students.end());

    size_t reserveNodes = 1ull + 20ull * (size_t)N + 8000000ull;
    seg.clear();
    seg.reserve(reserveNodes);
    seg.push_back({0, 0, 0});

    roots.assign(N + 1, 0);
    int idx = 0;
    for (int s = 1; s <= N; s++) {
        int root = roots[s - 1];
        while (idx < N && students[idx].first == s) {
            root = update_point(root, 1, N, students[idx].second);
            idx++;
        }
        roots[s] = root;
    }

    baseSizeAfterInit = seg.size();
}

int can(int M, int K[]) {
    vector<int> v;
    v.reserve(M);

    long long total = 0;
    for (int i = 0; i < M; i++) {
        v.push_back(K[i]);
        total += K[i];
        if (total > N) return 0;
    }

    sort(v.begin(), v.end());

    int used = 0;

    for (int i = 0; i < M; ) {
        int s = v[i];
        int cnt = 1;
        while (i + cnt < M && v[i + cnt] == s) cnt++;

        long long need_ll = 1LL * s * cnt;
        int need = (int)need_ll;

        int pref = roots[s];
        int avail = query_diff(pref, used, 1, N, s, N);
        if (avail < need) {
            seg.resize(baseSizeAfterInit);
            return 0;
        }

        int rem = need;
        used = consume_suffix(pref, used, 1, N, s, rem);

        i += cnt;
    }

    seg.resize(baseSizeAfterInit);
    return 1;
}

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