Submission #429144

#	Time	Username	Problem	Language	Result	Execution time	Memory
429144		timmyfeng	Teams (IOI15_teams)	C++17	77 / 100	1403 ms	524292 KiB

teams

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

const int N = 500001;

struct segtree {
    shared_ptr<segtree> left = nullptr, right = nullptr;
    int sum = 0;

    segtree() {}

    segtree(int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            left = make_shared<segtree>(l, m);
            right = make_shared<segtree>(m + 1, r);
        }
    }

    void pull() {
        sum = left->sum + right->sum;
    }

    shared_ptr<segtree> update(int a, int x, int l, int r) {
        shared_ptr<segtree> res = make_shared<segtree>();
        if (l == r) {
            res->sum = sum + x;
        } else {
            int m = (l + r) / 2;
            if (a <= m) {
                res->left = left->update(a, x, l, m);
                res->right = right;
            } else {
                res->left = left;
                res->right = right->update(a, x, m + 1, r);
            }
            res->pull();
        }
        return res;
    }
};

shared_ptr<segtree> copy(shared_ptr<segtree> u, shared_ptr<segtree> 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;
        shared_ptr<segtree> res = make_shared<segtree>();
        res->left = copy(u->left, v->left, a, b, l, m);
        res->right = copy(u->right, v->right, a, b, m + 1, r);
        res->pull();
        return res;
    }
}

shared_ptr<segtree> assign(shared_ptr<segtree> u, shared_ptr<segtree> v, int &k) {
    shared_ptr<segtree> res = make_shared<segtree>();
    if (!v->left) {
        int delta = min(k, u->sum - v->sum);
        res->sum = v->sum + delta;
        k -= delta;
        return res;
    } else if (u->sum - v->sum <= k) {
        k -= u->sum - v->sum;
        return u;
    } else {
        res->left = assign(u->left, v->left, k);
        res->right = k > 0 ? assign(u->right, v->right, k) : v->right;
        res->pull();
        return res;
    }
}

shared_ptr<segtree> root[N];
int 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] = make_shared<segtree>(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] = root[i]->update(students[j++][1], 1, 1, n);
        }
    }
}

bool can(int m, int k[]) {
    sort(k, k + m);
    shared_ptr<segtree> 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;
        }
    }
    return true;
}

Compilation message (stderr)

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

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