Ryhmät

#include <algorithm>
#include <iostream>
#include <limits>
#include <optional>
#include <set>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

constexpr int N = 1 << 17;

pair<int, int> toiveet[N];
vector<int> toivelistat[2 * N];
int koot[N];

struct Kulma {
    int x;
    int y;
    int s;
};

Kulma pino[N];

int summa_(int x1, int x2, int y, int v, int s) {
    if(x2 <= 0 || x1 >= s) {
        return 0;
    }
    if(x1 <= 0 && x2 >= s) {
        vector<int>& l = toivelistat[v];
        return (int)(lower_bound(l.begin(), l.end(), y) - l.begin());
    }
    int h = s >> 1;
    return summa_(x1, x2, y, 2 * v, h) + summa_(x1 - h, x2 - h, y, 2 * v + 1, h);
}

// [x1, x2[ x ]-oo, y[
int summa(int x1, int x2, int y) {
    return summa_(x1, x2, y, 1, N);
}

optional<int> kaannaSumma(int x1, int x2, int s) {
    if(summa(x1, x2, N) < s) {
        return nullopt;
    }
    int a = 0;
    int b = N;
    while(a < b) {
        int c = (a + b) / 2;
        int s2 = summa(x1, x2, c);
        if(s2 == s) {
            return c;
        }
        if(s2 < s) {
            a = c + 1;
        } else {
            b = c - 1;
        }
    }
    return a;
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);

    int n, t;
    cin >> n >> t;

    for(int i = 0; i < n; ++i) {
        cin >> toiveet[i].first >> toiveet[i].second;
    }
    sort(toiveet, toiveet + n, [&](pair<int, int> a, pair<int, int> b) { return a.second < b.second; });

    for(int i = 0; i < n; ++i) {
        auto [a, b] = toiveet[i];
        int v = N + a;
        while(v > 0) {
            toivelistat[v].push_back(i);
            v >>= 1;
        }
    }

    for(int ti = 0; ti < t; ++ti) {
        int m;
        cin >> m;
        for(int i = 0; i < m; ++i) {
            cin >> koot[i];
        }
        sort(koot, koot + m);

        int p = 0;
        pino[p++] = {-2, N + 2, 0};
        pino[p++] = {-1, N + 1, 0};

        int edellinenKoko = -1;
        bool onnistui = true;
        for(int kokoIdx = 0; kokoIdx < m; ++kokoIdx) {
            // if(p == 0) throw 5;
            // if(pino[0].x != -2) throw 5;
            // for(int i = 1; i < p; ++i) {
            //     if(pino[i].s != summa(pino[i - 1].x + 1, pino[i].x + 1, pino[i].y)) throw 5;
            // }

            const int koko = koot[kokoIdx];
            if(koko != edellinenKoko) {
                int y = lower_bound(toiveet, toiveet + n, make_pair(0, koko), [&](pair<int, int> a, pair<int, int> b) { return a.second < b.second; }) - toiveet;
                while(pino[p - 1].y <= y) {
                    --p;
                }
                pino[p] = {koko, y, summa(pino[p - 1].x + 1, koko + 1, y)};
                ++p;
            }
            edellinenKoko = koko;

            int jalj = koko;
            while(jalj) {
                int pala = summa(pino[p - 2].x + 1, pino[p - 1].x + 1, pino[p - 2].y) - pino[p - 1].s;
                if(jalj >= pala) {
                    if(p <= 2) {
                        onnistui = false;
                        goto ohi;
                    }
                    pino[p - 2].x = pino[p - 1].x;
                    pino[p - 2].s += pino[p - 1].s + pala;
                    --p;
                    jalj -= pala;
                } else {
                    optional<int> aOpt = kaannaSumma(pino[p - 2].x + 1, pino[p - 1].x + 1, pino[p - 1].s + jalj);
                    if(!aOpt.has_value()) {
                        onnistui = false;
                        goto ohi;
                    }
                    int a = aOpt.value();
                    // if(a > pino[p - 2].y - 1) throw 5;
                    // if(a > b) throw 5;
                    // if(summa(pino[p - 2].x + 1, pino[p - 1].x + 1, a) - pino[p - 1].s != jalj) throw 5;
                    pino[p - 1].y = a;
                    pino[p - 1].s += jalj;
                    jalj = 0;
                    // if(pino[p - 1].s != summa(pino[p - 2].x + 1, pino[p - 1].x + 1, pino[p - 1].y)) throw 5;
                    // if(pino[p - 2].y <= pino[p - 1].y) throw 5;
                }
            }
        }
        ohi: {}

        if(onnistui) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}

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: TIME LIMIT EXCEEDED

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