Novice F: Trolley Problem

Recall that the trolleys are sorted such that the heaviest trolleys go first, and the lightest ones go last. If a trolley gets stopped by a cow, what does that mean for the rest of the trolleys?

If we have a trolley get stopped by a cow, then we can direct subsequent trolleys to the same cow.

Once we have one cow that can stop a trolley, all subsequent trolleys can be directed to that same cow. This means that in our array of trolleys, we will have some prefix of trolleys that won't awaken a cow, while the rest of the trolleys will result in us waking up a cow.

Let's consider binary searching on the longest prefix of trolleys that won't awaken a cow. Consider checking if a prefix length of $$$m$$$ is valid.

Let the weight of the heaviest trolley in our prefix be $$$x$$$. We need to find the minimum index $$$i$$$, such that either $$$c[i] \geq x$$$ or $$$d[i] \geq x$$$.

If we are zero-indexing, $$$i$$$ is equal to the number of cows that must be awoken before finally reaching a cow heavy enough to stop our prefix of trolleys.

As long as $$$i$$$ is less than $$$n - m$$$, the number of trolleys not in our prefix, we can force all $$$m$$$ trolleys into a cow that is heavy enough.

Thus, with this condition, we can binary search on the longest prefix. The answer is then the number of trolleys that aren't in our prefix. With that, we can solve the problem in $$$\mathcal{O}(n \log n)$$$ time.

Note that an $$$\mathcal{O}(n)$$$ solution exists, but is slightly more difficult to implement.

#include <bits/stdc++.h>

using ll = long long;

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

    int n, a, b;
    std::cin >> n >> a >> b;
    std::vector<int> t(n), c(a), d(b);
    for (auto &i : t) std::cin >> i;
    for (auto &i : c) std::cin >> i;
    for (auto &i : d) std::cin >> i;

    int lo = 0, hi = n;
    while (lo < hi) {
        int m = (lo + hi + 1) / 2;

        int biggest = (m == 0) ? -1 : t[m - 1];
        int get_hit = std::min(a, b);

        for (int i = 0; i < a; i++) {
            if (biggest <= c[i]) get_hit = std::min(get_hit, i);
        }

        for (int i = 0; i < b; i++) {
            if (biggest <= d[i]) get_hit = std::min(get_hit, i);
        }

        if (get_hit <= n - m) lo = m;
        else hi = m - 1;
    }

    std::cout << n - lo << '\n';
}