72472024-01-05 11:10:31Error42Szurikáta (45)cpp17Accepted 45/4517ms9548 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";
}
SubtaskSumTestVerdictTimeMemory
base45/45
1Accepted0/03ms2108 KiB
2Accepted0/08ms2328 KiB
3Accepted2/23ms2348 KiB
4Accepted2/23ms2536 KiB
5Accepted2/24ms2928 KiB
6Accepted2/28ms3208 KiB
7Accepted2/28ms3392 KiB
8Accepted4/416ms4992 KiB
9Accepted4/414ms5496 KiB
10Accepted4/414ms6336 KiB
11Accepted4/414ms7052 KiB
12Accepted4/414ms7536 KiB
13Accepted5/516ms7988 KiB
14Accepted5/517ms8864 KiB
15Accepted5/517ms9548 KiB