We are given ~N~ henchmen and ~M~ doors located at distinct positions on the number line. Henchman ~j~ is in Bond's line of sight if and only if every door ~i~ with ~D_i~ value less than ~H_j~ is opened. That is, for the ~i~-th line of output, we should count the number of henchmen such that no ~D~ value from ~i+1~ to ~M~ is greater than ~H~. To illustrate the intended computations, a naïve solution is given here which runs in ~\mathcal O(NM^2)~.

#include <iostream>
using namespace std;

int N, M, H[200005], D[200005];

int main() {
  cin >> N >> M;
  for (int i = 0; i < N; i++) cin >> H[i];
  for (int i = 0; i < M; i++) cin >> D[i];
  for (int i = 0; i < M; i++) {
    int ans = 0;
    for (int j = 0; j < N; j++) {
      bool blocked = false;
      for (int k = i + 1; k < M; k++)
        if (D[i] < H[j]) blocked = true;
      if (!blocked) ans++;
    }
    cout << ans << endl;
  }
  return 0;
}

This solution is only meant to be given only 3/17 of the points (through the first subtask, where ~N, M \le 100~, so ~NM^2~ is no larger than ~100^3 = 1\,000\,000~). The second subtask was designed for various ~\mathcal O(MN \log N)~ solutions which we will not discuss here.

For up to the third subtask, we can go for an ~\mathcal O(NM)~ solution which eliminates the innermost for-loop of k. How? Observe that the inner loop is asking the question "does there exist a value in ~D[(i+1) \dots M]~ which is less than the current ~H[j]~?" This is actually equivalent to asking if the minimum value in ~D[(i+1) \dots M]~ is less than ~H[i]~. Let the array ~minD[]~ be such that ~minD[i]~ stores the minimum ~D~ value from ~i~ to ~M~. To compute this array, just loop backwards from ~M~ to ~1~ and store the minimum of the minimum so far with the current ~D~ value. This simple solution is given 11/17 of the points.

It is also possible to get 11/17 points with a more complex solution, which involves sorting, searching, and erasing from an array.

For a full solution, let's start by sorting the ~N~ henchmen in increasing order of position, which can be done using any ~\mathcal O(N \log N)~ time sorting algorithm. Let's similarly sort the ~M~ doors in ~\mathcal O(M \log M)~ time – however in this case, we'll need to keep each door's original index associated with its position after the sort (as opposed to only sorting the ~M~ door positions independently, where info about the original position is lost). To accomplish this, we can represent each door as a pair of integers ~(\text{position}, \text{original index})~, and compare these pairs by only their position value in the sorting algorithm. To use this with the built-in sorting function of certain languages, we may need to define a custom class and/or comparator, or use something like C++'s std::pair.

Now, as we simulate opening all of the doors in order, we'd like to maintain one running index for each of the two sorted lists. Firstly, we need to keep track of the index ~h~ of the current first henchmen not in Bond's line of fire (or ~N+1~ if there's no such henchman). Secondly, we need the index ~d~ of the current first closed door (or ~M+1~ if there's no such door). We can observe that exactly the first ~h-1~ sorted henchmen will be in Bond's line of fire, such that the ~h~-th henchmen is the first one further from Bond than the ~d~-th door in the sorted list.

When door ~i~ is opened, we can update ~d~ by repeatedly incrementing it as long as it's no larger than ~M~, and the original index of the ~d~-th door in the sorted list is smaller than or equal to ~i~ (note that ~d~ never decreases). When a given door is opened, ~d~ might stay the same or be incremented many times, but over the course of the entire simulation, it will only be incremented ~M~ times, so these updates will take ~\mathcal O(M)~ time in total.

After the index ~d~ has been updated for door ~i~, we can use it to update ~h~ accordingly (which will give us the ~i~-th answer). Similarly to the above approach, we can repeatedly increment ~h~ as long as it's no larger than ~N~, and the index of the ~h~-th henchman in the sorted list is before the index of the ~d~-th door in the sorted list. Likewise, ~i~ will be incremented a total of ~N~ times throughout the entire simulation, which can be handled in ~\mathcal O(N)~ time.

The sorting of the two arrays dominate over the simulation, so the overall running time is ~\mathcal O(N \log N + M \log M)~.

Alternatively, we don't have to keep track of the ~h~ value. In this case, the second while-loop may be replaced with a binary search on the sorted array of henchmen, querying for the first henchman position which is not less than the position of the current door. This position is the answer, since all henchmen before will also be in the line of sight.

Alternatively, we can put all henchmen and doors into the same array of pairs and sort them by position (but still remembering the index of each door). When we open a door, we erase the door ~i~ from the sorted array and loop ~d~ upwards until we skip over all of the erased doors while counting the number of henchmen encountered in the same loop. The sorting also dominates in this variation, but as we are sorting a list of size ~N+M~, the solution will run in ~\mathcal O((N+M) \log(N+M))~ time.