Submission #429165

#	Time	Username	Problem	Language	Result	Execution time	Memory
429165		timmyfeng	Teams (IOI15_teams)	C++17	100 / 100	1459 ms	207264 KiB

teams

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

const int N = 500001, S = 64 * N;

int sum[S], child[S][2], ptr = 1;

int segtree(int x) {
    child[ptr][0] = child[ptr][1] = 0;
    sum[ptr] = x;
    return ptr++;
}

int segtree(int l, int r) {
    child[ptr][0] = l, child[ptr][1] = r;
    sum[ptr] = sum[l] + sum[r];
    return ptr++;
}

int build(int l, int r) {
    int u = segtree(0);
    if (l < r) {
        int m = (l + r) / 2;
        child[u][0] = build(l, m);
        child[u][1] = build(m + 1, r);
    }
    return u;
}

int update(int u, int a, int x, int l, int r) {
    if (l == r) {
        return segtree(sum[u] + x);
    } else {
        int m = (l + r) / 2;
        if (a <= m) {
            return segtree(update(child[u][0], a, x, l, m), child[u][1]);
        } else {
            return segtree(child[u][0], update(child[u][1], a, x, m + 1, r));
        }
    }
}

int copy(int u, int v, int a, int b, int l, int r) {
    if (b < a || b < l || r < a) {
        return v;
    } else if (a <= l && r <= b) {
        return u;
    } else {
        int m = (l + r) / 2;
        return segtree(
            copy(child[u][0], child[v][0], a, b, l, m),
            copy(child[u][1], child[v][1], a, b, m + 1, r)
        );
    }
}

int assign(int u, int v, int &k) {
    if (child[v][0] == 0) {
        int delta = min(k, sum[u] - sum[v]);
        k -= delta;
        return segtree(sum[v] + delta);
    } else if (sum[u] - sum[v] <= k) {
        k -= sum[u] - sum[v];
        return u;
    } else {
        int l = assign(child[u][0], child[v][0], k);
        int r = k > 0 ? assign(child[u][1], child[v][1], k) : child[v][1];
        return segtree(l, r);
    }
}

int root[N], n;
 
void init(int n, int a[], int b[]) {
    ::n = n;
    vector<array<int, 2>> students;
    for (int i = 0; i < n; ++i) {
        students.push_back({a[i], b[i]});
    }
    sort(students.begin(), students.end());
 
    root[0] = build(1, n);
    for (int i = 1, j = 0; i <= n; ++i) {
        root[i] = root[i - 1];
        while (j < n && students[j][0] == i) {
            root[i] = update(root[i], students[j++][1], 1, 1, n);
        }
    }
}
 
bool can(int m, int k[]) {
    int temp = ptr;
    sort(k, k + m);
    int used = root[0];
    for (int i = 0; i < m; ++i) {
        used = copy(root[k[i]], used, 1, k[i] - 1, 1, n);
        used = assign(root[k[i]], used, k[i]);
        if (k[i] > 0) {
            return false;
        }
    }
    ptr = temp;
    return true;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:74:15: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   74 | void init(int n, int a[], int b[]) {
      |           ~~~~^
teams.cpp:72:14: note: shadowed declaration is here
   72 | int root[N], n;
      |              ^

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