Ryhmät

input/code.cpp: In member function 'bool mybits::poista(const mybits&, int)':
input/code.cpp:69:59: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
   69 |             for (int shl_min = 0, shl_max = slice_size; c > määrä;) {
      |                                                         ~~^~~~~~~
input/code.cpp:73:24: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
   73 |                 if (c2 == määrä) {
      |                     ~~~^~~~~~~~
input/code.cpp:77:24: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
   77 |                 if (c2 > määrä) {
      |                     ~~~^~~~~~~

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <bitset>

using namespace std;

struct Toive {
    int alku, loppu, indeksi;
};

struct mybits {
    constexpr static int slice_size = 512;
    constexpr static int slice_count = 100001 / slice_size + 1;
    typedef bitset<slice_size> slice_type;

    bitset<slice_count> oletus;
    unordered_map<int, slice_type> data;

    mybits(bool alkuarvo) {
        if (alkuarvo) {
            oletus.set();
        }
    }
    bool empty(int idx) const {
        return !oletus[idx] && !data.contains(idx);
    }
    slice_type slice(int idx) const {
        if (data.contains(idx)) {
            return data.at(idx);
        }
        if (oletus[idx]) {
            return slice_type().set();
        }
        return slice_type();
    }
    void put(int idx, const slice_type& value) {
        if (value == slice_type().set() || value.none()) {
            oletus[idx] = value.test(0);
            data.erase(idx);
            return;
        }
        data[idx] = value;
    }
    void set(int i, bool value) {
        int idx = i / slice_size;
        int bit = i % slice_size;
        auto a = slice(idx);
        a.set(bit, value);
        put(idx, a);
    }
    bool poista(const mybits& other, int määrä) {
        for (int i = 0; i < slice_count && määrä; i++) {
            if (empty(i) || other.empty(i)) {
                continue;
            }
            auto old = slice(i);
            auto a = old & other.slice(i);
            auto c = a.count();
            if (!c) {
                continue;
            }
            for (int shl_min = 0, shl_max = slice_size; c > määrä;) {
                int shl = (shl_min + shl_max) / 2;
                auto a2 = (a << shl) >> shl;
                auto c2 = a2.count();
                if (c2 == määrä) {
                    put(i, old ^ a2);
                    return true;
                }
                if (c2 > määrä) {
                    shl_min = shl;
                } else {
                    shl_max = shl;
                }
            }
            määrä -= c;
            put(i, old ^ a);
        }
        return määrä == 0;
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n, t;
    cin >> n >> t;
    vector<pair<int, int>> toiveet_loppu_alku(n), toiveet_alku_indeksi(n);
    for (int i = 0; i < n; i++) {
        cin >> toiveet_loppu_alku[i].second >> toiveet_loppu_alku[i].first;
    }
    ranges::sort(toiveet_loppu_alku);
    for (int i = 0; i < n; i++) {
        toiveet_alku_indeksi[i] = {toiveet_loppu_alku[i].second, i};
    }
    ranges::sort(toiveet_alku_indeksi);

    vector<bool> tulokset(t);
    vector<array<int, 3>> vaiheet;

    for (int testi = 0; testi < t; testi++) {
        tulokset[testi] = true;
        int ryhmien_määrä;
        cin >> ryhmien_määrä;
        map<int, int> ryhmät;
        for (int i = 0; i < ryhmien_määrä; i++) {
            int ryhmän_koko;
            cin >> ryhmän_koko;
            ryhmät[ryhmän_koko] += ryhmän_koko;
        }
        for (auto &[koko, lapsimäärä] : ryhmät) {
            vaiheet.push_back({koko, lapsimäärä, testi});
        }
    }
    ranges::sort(vaiheet);

    mybits kaikki_vapaana(true);
    vector<mybits> vapaat(t, kaikki_vapaana);

    auto toive_iter = toiveet_alku_indeksi.begin();
    set<int> toiveet_kesken;
    mybits toiveet_bits(false);
    for (auto &[koko, lapsimäärä, testi] : vaiheet) {
        if (tulokset[testi] == false) {
            continue;
        }
        while (toive_iter != toiveet_alku_indeksi.end() && toive_iter->first <= koko) {
            int indeksi = toive_iter->second;
            toiveet_kesken.insert(indeksi);
            toiveet_bits.set(indeksi, true);
            toive_iter++;
        }
        while (!toiveet_kesken.empty() && toiveet_loppu_alku[*toiveet_kesken.begin()].first < koko) {
            int indeksi = *toiveet_kesken.begin();
            toiveet_kesken.erase(toiveet_kesken.begin());
            toiveet_bits.set(indeksi, false);
        }
        if (!vapaat[testi].poista(toiveet_bits, lapsimäärä)) {
            tulokset[testi] = false;
        }
    }

    for (auto tulos : tulokset) {
        if (tulos) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: ACCEPTED