Ryhmät

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

    array<slice_type, slice_count> data;

    mybits(bool alkuarvo = false) {
        if (alkuarvo) {
            for (auto& s : data) {
                s.set();
            }
        }
    }
    void set(int i, bool value) {
        int idx = i / slice_size;
        int bit = i % slice_size;
        data[idx][bit] = value;
    }
    bool poista(const mybits& other, int määrä) {
        for (int i = 0; i < slice_count && määrä; i++) {
            auto a = data[i] & other.data[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ä) {
                    data[i] ^= a2;
                    return true;
                }
                if (c2 > määrä) {
                    shl_min = shl;
                } else {
                    shl_max = shl;
                }
            }
            määrä -= c;
            data[i] ^= 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<int> summataulu(n + 1);
    for (auto &[loppu, alku] : toiveet_loppu_alku) {
        summataulu[alku]++;
        summataulu[loppu + 1]--;
    }
    for (int i = 0; i < n; i++) {
        summataulu[i + 1] = summataulu[i] + summataulu[i + 1];
    }

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

    mybits kaikki_vapaana(true);
    unordered_map<int, mybits> vapaat;

    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;
        }
        if (ryhmät.size() == 1) {
            auto &[koko, lapsimäärä] = *ryhmät.begin();
            tulokset[testi] = summataulu[koko] >= lapsimäärä;
        } else for (auto &[koko, lapsimäärä] : ryhmät) {
            vapaat[testi] = kaikki_vapaana;
            vaiheet.push_back({koko, lapsimäärä, testi});
        }
    }
    ranges::sort(vaiheet);

    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: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED