7247 2024. 01. 05 11:10:31 Error42 Szurikáta (45) cpp17 Elfogadva 45/45 17ms 9548 KiB
#include <algorithm>
#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

using ll = long long;

struct point {
    ll x, y;

    bool operator ==(point const& rhs) const {
        return x == rhs.x && y == rhs.y;
    }
};

int turn(point const& a, point const& b, point const& c) {
    ll const s = (c.y - a.y) * (b.x - a.x) - (b.y - a.y) * (c.x - a.x);
    return (s > 0) - (s < 0);
}

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

    ll n, p, q;
    cin >> n >> p >> q;

    point const bird = { 0, p };

    auto const blocks = [&](point const& a, point const& b) {
        return turn(bird, a, b) <= 0;
    };

    vector<point> meerkats(n);
    for (point& meerkat : meerkats)
        cin >> meerkat.x;
    for (point& meerkat : meerkats)
        cin >> meerkat.y;

    vector<point> def;
    vector<int> pos;

    {
        point best = { 0, 0 };

        for (point const& meerkat : meerkats) {
            if (!blocks(best, meerkat)) {
                def.push_back(meerkat);
                best = meerkat;
            }

            pos.push_back(def.size() - 1);
        }
    }

    auto const in_def = [&](int const mi) {
        return def[pos[mi]] == meerkats[mi];
    };

    while (q--) {
        ll db;
        cin >> db;

        vector<point> updated(db);
        for (point& u : updated) {
            cin >> u.x >> u.y;
            u.x--;
        }

        int sees = def.size();

        point best = { 0, 0 };

        for (int ui = 0; ui < updated.size(); ui++) {
            ll const mi = updated[ui].x;
            ll const dy = updated[ui].y;

            point const peeking = { meerkats[mi].x, meerkats[mi].y + dy };

            if (in_def(mi)) {
                if (blocks(best, peeking))
                    sees--;
                else
                    best = peeking;
            }
            else {
                if (!blocks(best, def[pos[mi]]))
                    best = def[pos[mi]];

                if (!blocks(best, peeking)) {
                    sees++;
                    best = peeking;
                }
            }

            int const until = ui + 1 < updated.size()
                ? pos[updated[ui + 1].x] + (in_def(updated[ui + 1].x) ?  -1 : 0)
                : def.size() - 1;

            int const first_not_blocked = lower_bound(def.begin() + pos[mi] + 1, def.begin() + until + 1, 0, [&](point const& a, int const& _) {
                return blocks(best, a);
            }) - def.begin();

            sees -= first_not_blocked - (pos[mi] + 1);
        }

        cout << sees << " ";
    }

    cout << "\n";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 45/45
1 Elfogadva 0/0 3ms 2108 KiB
2 Elfogadva 0/0 8ms 2328 KiB
3 Elfogadva 2/2 3ms 2348 KiB
4 Elfogadva 2/2 3ms 2536 KiB
5 Elfogadva 2/2 4ms 2928 KiB
6 Elfogadva 2/2 8ms 3208 KiB
7 Elfogadva 2/2 8ms 3392 KiB
8 Elfogadva 4/4 16ms 4992 KiB
9 Elfogadva 4/4 14ms 5496 KiB
10 Elfogadva 4/4 14ms 6336 KiB
11 Elfogadva 4/4 14ms 7052 KiB
12 Elfogadva 4/4 14ms 7536 KiB
13 Elfogadva 5/5 16ms 7988 KiB
14 Elfogadva 5/5 17ms 8864 KiB
15 Elfogadva 5/5 17ms 9548 KiB