Submission #727811

#	Time	Username	Problem	Language	Result	Execution time	Memory
727811		nenechan	Teams (IOI15_teams)	C++17	0 / 100	798 ms	524288 KiB

teams

#include "teams.h"

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

// The solution for a single Q would be as follow:
// - Consider all the task in increasing order of required students
// - For each required value x in that order, greedily accept students who have A <= x and lowest B possible.
// - Complexity is O(N log(N)) if using a heap as priority queue.

// Assume K is sorted increasing

// if M is 1, then we have the following solution:
// - instead of having to insert and decrease, we can just count the number of people who can work with the required condition,
// and be done with it.

// if M is 2, then the following solution has some problem:
// - after we count the number of people who can do K[0]
// - and the number of people who can do K[1]
// - the 2 sets might intersect, so it could be that both can be done, but not at the same time.
// - to fix this, we can count the number of people who can do K[0], the number of people who can do K[1], and the number of
// people who can do both
// - let the value be X, Y, and Z
// - then the condition can be rewritten as max(0, K[0] - (X - Z)) + max(0, K[1] - (Y - Z)) <= Z

// generalize:
// - First we will check the number of people who can do K[0]
// - Then we check the number of people who can do K[0] but not K[1]
//   - These people also can't do K[2] and so on
// - If the number of people who can do only K[0] is >= K[0], then we don't have to care, and only solve the problem for K[1] on
// ward
// - Otherwise anyone who else can do K[0], must also be able to do K[1]
// - Which mean we can treat the rest of K[0] as K[1] as well, and solve the problem for K[1] onward
// - Note that if multiple K[i] is equal, merge them
// - So the main query become:
//   - Count the number of people who can do K[i]
//   - Count the number of people who can do K[i] but not K[i + 1]
// - So count A[i] <= x and B[i] >= x and B[i] <= y
// -> persistent segment tree
class persistent_segment_tree_t {
public:
    persistent_segment_tree_t *left, *right;
    int l, r, m;
    int count;

    persistent_segment_tree_t(const int& l, const int& r) : l(l), r(r), m((l + r) / 2), count(0) {
        if (l != r) {
            left = new persistent_segment_tree_t(l, m);
            right = new persistent_segment_tree_t(m + 1, r);
        }
    }

    persistent_segment_tree_t(const persistent_segment_tree_t* other) { *this = *other; }

    persistent_segment_tree_t* update(const int& u) const {
        auto new_tree = new persistent_segment_tree_t(this);
        new_tree->count++;
        if (l != r) {
            if (m >= u) new_tree->left = left->update(u);
            else new_tree->right = right->update(u);
        }
        return new_tree;
    }

    int get(const int& u, const int& v) const {
        if (l > v || r < u) return u;
        if (u <= l && v >= r) return count;
        return left->get(u, v) + right->get(u, v);
    }
};
persistent_segment_tree_t* tree[500001];
vector<pair<int, int>> s;
int n;
void init(int N, int A[], int B[]) {
    n = N;
    for (int i = 0; i < n; i++) s.emplace_back(A[i], B[i]);
    sort(s.begin(), s.end());
    tree[0] = new persistent_segment_tree_t(1, n);

    for (int i = 1, j = 0; i <= n; i++) {
        tree[i] = tree[i - 1];
        while ((j < n) && (s[j].first <= i)) {
            tree[i] = tree[i]->update(s[j].second);
            j++;
        }
    }
}

int can(int M, int K[]) {
    if (accumulate(K, K + M, 0LL) > n) return 0;
    sort(K, K + M);
    int left_over = 0;
    for (int i = 0; i < M; i++) {
        int j = i;
        while (((j + 1) < M) && (K[j + 1] == K[j])) j++;
        if (i) left_over = max(0, left_over - tree[K[i - 1]]->get(K[i - 1], K[i] - 1));
        left_over += (j - i + 1) * K[i];
        if (left_over > tree[K[i]]->get(K[i], 1e9)) return 0;
        i = j;
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In constructor 'persistent_segment_tree_t::persistent_segment_tree_t(const int&, const int&)':
teams.cpp:46:56: warning: declaration of 'r' shadows a member of 'persistent_segment_tree_t' [-Wshadow]
   46 |     persistent_segment_tree_t(const int& l, const int& r) : l(l), r(r), m((l + r) / 2), count(0) {
      |                                             ~~~~~~~~~~~^
teams.cpp:43:12: note: shadowed declaration is here
   43 |     int l, r, m;
      |            ^
teams.cpp:46:42: warning: declaration of 'l' shadows a member of 'persistent_segment_tree_t' [-Wshadow]
   46 |     persistent_segment_tree_t(const int& l, const int& r) : l(l), r(r), m((l + r) / 2), count(0) {
      |                               ~~~~~~~~~~~^
teams.cpp:43:9: note: shadowed declaration is here
   43 |     int l, r, m;
      |         ^
teams.cpp: In constructor 'persistent_segment_tree_t::persistent_segment_tree_t(const int&, const int&)':
teams.cpp:46:56: warning: declaration of 'r' shadows a member of 'persistent_segment_tree_t' [-Wshadow]
   46 |     persistent_segment_tree_t(const int& l, const int& r) : l(l), r(r), m((l + r) / 2), count(0) {
      |                                             ~~~~~~~~~~~^
teams.cpp:43:12: note: shadowed declaration is here
   43 |     int l, r, m;
      |            ^
teams.cpp:46:42: warning: declaration of 'l' shadows a member of 'persistent_segment_tree_t' [-Wshadow]
   46 |     persistent_segment_tree_t(const int& l, const int& r) : l(l), r(r), m((l + r) / 2), count(0) {
      |                               ~~~~~~~~~~~^
teams.cpp:43:9: note: shadowed declaration is here
   43 |     int l, r, m;
      |         ^
teams.cpp: In constructor 'persistent_segment_tree_t::persistent_segment_tree_t(const int&, const int&)':
teams.cpp:46:56: warning: declaration of 'r' shadows a member of 'persistent_segment_tree_t' [-Wshadow]
   46 |     persistent_segment_tree_t(const int& l, const int& r) : l(l), r(r), m((l + r) / 2), count(0) {
      |                                             ~~~~~~~~~~~^
teams.cpp:43:12: note: shadowed declaration is here
   43 |     int l, r, m;
      |            ^
teams.cpp:46:42: warning: declaration of 'l' shadows a member of 'persistent_segment_tree_t' [-Wshadow]
   46 |     persistent_segment_tree_t(const int& l, const int& r) : l(l), r(r), m((l + r) / 2), count(0) {
      |                               ~~~~~~~~~~~^
teams.cpp:43:9: note: shadowed declaration is here
   43 |     int l, r, m;
      |         ^

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