Ryhmät

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    int n, t;
    cin >> n >> t;
    vector<pair<int, int>> toiveet(n);
    vector<pair<int, int>> toiveet_rev(n);
    for (int i = 0; i < n; i++) {
        cin >> toiveet[i].first >> toiveet[i].second;
        toiveet_rev[i] = {toiveet[i].second, toiveet[i].first};
    }
    sort(toiveet.begin(), toiveet.end());
    sort(toiveet_rev.begin(), toiveet_rev.end());
    vector<int> toiveet_delta(n + 1);
    for (auto &[alku, loppu] : toiveet) {
        toiveet_delta[alku]++;
        toiveet_delta[loppu + 1]--;
    }
    vector<int> toiveet_maksimi(n + 1);
    toiveet_maksimi[0] = toiveet_delta[0];
    for (int i = 0; i <= n; i++) {
        toiveet_maksimi[i] = toiveet_maksimi[i - 1] + toiveet_delta[i];
    }
    for (int _ = 0; _ < t; _++) {
        if (0) {
            ei:;
            cout << "NO\n";
            continue;
        }
        int ryhmien_maara;
        cin >> ryhmien_maara;
        map<int, int> ryhmät;
        for (int i = 0; i < ryhmien_maara; i++) {
            int ryhmän_koko;
            cin >> ryhmän_koko;
            ryhmät[ryhmän_koko] += ryhmän_koko;
            if (ryhmät[ryhmän_koko] > toiveet_maksimi[ryhmän_koko]) {
                // Liian monta lasta, joilla on sama ryhmän koko
                goto ei;
            }
        }
        priority_queue<int> toiveet_alkaneet;
        int toive_i = 0;
        for (auto &[koko, lapsimäärä] : ryhmät) {
            while (!toiveet_alkaneet.empty() && -toiveet_alkaneet.top() < koko) {
                toiveet_alkaneet.pop();
            }
            while (toive_i < n && toiveet[toive_i].first <= koko) {
                toiveet_alkaneet.push(-toiveet[toive_i].second);
                toive_i++;
            }
            while (!toiveet_alkaneet.empty() && -toiveet_alkaneet.top() < koko) {
                toiveet_alkaneet.pop();
            }
            for (int lapsi = 0; lapsi < lapsimäärä; lapsi++) {
                if (toiveet_alkaneet.empty()) {
                    goto ei;
                } else {
                    toiveet_alkaneet.pop();
                }
            }
        }
        cout << "YES\n";
    }
}

Test 1

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 2

Group: 1, 2, 3

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: WRONG ANSWER

Test 11

Group: 3

Verdict: WRONG ANSWER

Test 12

Group: 3

Verdict: WRONG ANSWER

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED