Submission #639895

#	Time	Username	Problem	Language	Result	Execution time	Memory
639895		piOOE	Teams (IOI15_teams)	C++17	100 / 100	890 ms	200200 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

constexpr int N = 500001, N_ = (N + 400001) * 19;

int cnt[N_ + 1], L[N_ + 1], R[N_ + 1], sz = 1, root[N];

int create(int val, int l, int r) {
    int x = sz++;
    cnt[x] = val, L[x] = l, R[x] = r;
    return x;
}

int modify(int x, int lx, int rx, int i) {
    int nx = create(cnt[x] + 1, L[x], R[x]);
    if (lx + 1 < rx) {
        int mid = (lx + rx) >> 1;
        if (i < mid) {
            L[nx] = modify(L[x], lx, mid, i);
        } else {
            R[nx] = modify(R[x], mid, rx, i);
        }
    }
    return nx;
}

int n;

void init(int n_, int A[], int B[]) {
    n = n_;
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return A[i] < A[j];
    });
    int j = 0, x = 0;
    for (int i = 0; i <= n; ++i) {
        while (j < n && A[ord[j]] == i) {
            x = modify(x, 0, n, B[ord[j++]] - 1);
        }
        root[i] = x;
    }
}

int query(int x, int u, int lx, int rx, int i, int &k) {
    if (rx <= i || k == 0) return u;
    if (lx >= i && k >= cnt[x] - cnt[u]) {
        k -= cnt[x] - cnt[u];
        return x;
    }
    int mid = (lx + rx) >> 1;
    int nu = sz++;
    if (lx + 1 < rx) {
        L[nu] = query(L[x], L[u], lx, mid, i, k);
        R[nu] = query(R[x], R[u], mid, rx, i, k);
        cnt[nu] = cnt[L[nu]] + cnt[R[nu]];
    } else {
        cnt[nu] = cnt[u] + k;
        k = 0;
    }
    return nu;
}

int can(int m, int K[]) {
    if (accumulate(K, K + m, 0ll) > n) {
        return 0;
    }
    sort(K, K + m);
    int used = 0;
    for (int i = 0; i < m; ++i) {
        int k = K[i];
        used = query(root[k], used, 0, n, k - 1, k);
        if (k > 0) {
            return 0;
        }
    }
    return 1;
}

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