Ryhmät

#include <algorithm>
#include <iostream>
#include <limits>
#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);
}

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++] = {-1, N, 0};

        int edellinenKoko = -1;
        bool onnistui = true;
        for(int kokoIdx = 0; kokoIdx < m; ++kokoIdx) {
            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;

            if(p == 0) 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;
            }

            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 == 1) {
                        onnistui = false;
                        goto ohi;
                    }
                    pino[p - 2].x = pino[p - 1].x;
                    pino[p - 2].s += pino[p - 1].s + pala;
                    if(pino[p - 1].s != summa(pino[p - 2].x + 1, pino[p - 1].x + 1, pino[p - 1].y)) throw 5;
                    --p;
                    jalj -= pala;
                } else {
                    int a = pino[p - 1].y + 1;
                    int b = pino[p - 2].y - 1;
                    while(a < b) {
                        int c = (a + b) / 2;
                        int s = summa(pino[p - 2].x + 1, pino[p - 1].x + 1, c) - pino[p - 1].s;
                        if(s == jalj) {
                            a = c;
                            b = c;
                        } else if(s < jalj) {
                            a = c + 1;
                        } else {
                            b = c - 1;
                        }
                    }
                    if(a == pino[p - 2].y) {
                        onnistui = false;
                        goto ohi;
                    }
                    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: RUNTIME ERROR

terminate called after throwing an instance of 'int'

Test 2

Group: 1, 2, 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'int'

Test 3

Group: 1, 2, 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'int'

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'int'

Test 6

Group: 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'int'

Test 7

Group: 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'int'

Test 8

Group: 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'int'

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'int'

Test 11

Group: 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'int'

Test 12

Group: 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'int'

Test 13

Group: 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'int'

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'int'

Test 16

Group: 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'int'