Subtask 2: $H=1$

The $i$th card FJ chooses must be the $(i-1)\pmod N+1$'th card in the input. We can answer a query for $t$ by:

1. Dividing $t$ by the time it takes to cycle through all $N$ cards to get the number of full cycles.
2. Using binary search on prefix sums of card costs to count the number of additional cards played.

Full Solution:

Let's represent each card with an ordered pair $(-[\text{is win condition}], a_i)$. Then if FJ is deciding between two cards to choose,

• If their pairs have different first elements, he must choose the smaller pair (the one that's a win-condition).
• Otherwise, he should always choose the card with smaller cost.

So in general, FJ will always take the card in his hand labeled with the lexicographically smallest pair. We can maintain the cards currently in FJ's hand in a priority queue and simulate $N-H+1$ draws. After this, FJ will simply cycle through the same $N-H+1$ cards over and over again. To see why this is true, observe that

• Out of the globally smallest $N-H+1$ cards, at least one will always be in FJ's hand, so these are the only cards FJ will play.
• After $N-H+1$ draws, the only card out of the globally smallest $N-H+1$ that are in FJ's hand will be the first card FJ played. Same for every step after that: the only card available to play will be the card FJ played $N-H+1$ draws ago.

So the rest of the solution is similar to subtask 2, just with a different number of cards in the cycle.

#include <bits/stdc++.h>
using namespace std;

template <class T> using V = vector<T>;
#define all(x) begin(x), end(x)

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, H;
    cin >> N >> H;

    using P = pair<int, int>;
    V<P> A(N);
    for (auto &p : A) cin >> p.second;

    int K;
    cin >> K;
    for (int i = 0; i < K; ++i) {
        int s;
        cin >> s;
        --s;
        A.at(s).first = -1;
    }

    priority_queue<P, V<P>, greater<P>> pq;

    for (int i = 0; i < H - 1; ++i) pq.push(A.at(i));
    V<ll> cycle;  // time each win-condition in cycle is played
    ll cycle_len = 0;
    for (int i = 0; i <= N - H; ++i) {
        pq.push(A.at(i + H - 1));
        cycle_len += pq.top().second;
        if (pq.top().first == -1) cycle.push_back(cycle_len);
        pq.pop();
    }
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; ++i) {
        ll t;
        cin >> t;
        ll ans = t / cycle_len * size(cycle);
        ans +=
            upper_bound(begin(cycle), end(cycle), t % cycle_len) - begin(cycle);
        cout << ans << "\n";
    }
}