Ryhmät

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

using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    int n, t;
    cin >> n >> t;
    multimap<int, Toive> toiveet;
    for (int i = 0; i < n; i++) {
        Toive tmp;
        cin >> tmp.alku >> tmp.loppu;
        tmp.indeksi = i;
        toiveet.insert({tmp.alku, tmp});
    }

    vector<bool> tulokset(t, true);
    vector<array<int, 3>> vaiheet;
    vector<unordered_set<int>> käytetyt(t);
    for (int testi = 0; testi < t; testi++) {
        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);

    auto& toiveet_tulossa = toiveet;
    multimap<int, Toive> toiveet_alkaneet;
    for (auto &[koko, lapsimäärä, testi] : vaiheet) {
        if (tulokset[testi] == false) {
            continue;
        }
        while (!toiveet_tulossa.empty() && toiveet_tulossa.begin()->first <= koko) {
            auto toive = toiveet_tulossa.begin()->second;
            toiveet_alkaneet.insert({toive.loppu, toive});
            toiveet_tulossa.erase(toiveet_tulossa.begin());
        }
        while (!toiveet_alkaneet.empty() && toiveet_alkaneet.begin()->first < koko) {
            toiveet_alkaneet.erase(toiveet_alkaneet.begin());
        }
        for (auto [loppu, toive] : toiveet_alkaneet) {
            if (käytetyt[testi].find(toive.indeksi) == käytetyt[testi].end()) {
                käytetyt[testi].insert(toive.indeksi);
                lapsimäärä--;
                if (lapsimäärä == 0) {
                    break;
                }
            }
        }
        if (lapsimäärä > 0) {
            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: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED