1112. Is This Line-Up Consistent

A line of n people is given IN ORDER, front to back. For each person you are told their height h and a number k, which is claimed to be how many people ahead of them in the line are at least as tall as they are.

Print yes if every claim is correct, and no otherwise.

5 0 / 7 0 / 5 2 / 6 1 / 4 4 / 7 1 -> yes 7 0 / 4 4 / 7 1 / 5 0 / 6 1 / 5 2 -> no 3 0 / 3 1 -> yes 3 0 / 3 0 -> no

## The partner problem

Problem 1083 is given the same people SCRAMBLED and must rebuild the order. This one is given an order and must check it.

The pair is worth solving together because the two are not the same difficulty and not the same technique. Building requires an insertion argument and produces one answer. Checking requires only that each claim be recomputed, and it is the cheaper half. Notice also that 1083's input is guaranteed consistent, while here inconsistency is the whole question.

The two sample inputs above are the same six people. The first is the order 1083 would build for them; the second is the scrambled order 1083 receives, and it does not satisfy the claims.

## The obvious method, and why it is too slow

For each person, walk everyone ahead of them and count the ones at least as tall. That is O(n^2), which at n = 10^5 is 10^10 comparisons.

## Count as you walk

Walk the line from front to back, keeping a tally of the heights placed so far. At each person, the answer to their claim is how many placed heights are at least h, which is

(people placed so far) - (people placed so far with height strictly below h)

Compare it with k and stop at the first mismatch. Nothing behind the current person can affect their claim, which is what makes one forward pass enough.

## The structure that makes it fast

A Fenwick tree over the height values supports both operations in O(log H): add one occurrence of a height, and count how many placed heights are below a given value.

Heights are bounded by 10^5, so the tree is indexed directly by height with no compression. A plain counting array does not work here, because answering "how many are below h" from it costs O(H) per person.

## Where the off-by-one lives

The claim counts people at least as tall, so the query must be for heights STRICTLY BELOW h, subtracted from the total placed. Querying "at most h" instead counts the person's own height class as shorter than itself and undercounts every tie.

The pair 3 0 / 3 1 answers yes and 3 0 / 3 0 answers no, and those two inputs differ only in that count. They are the cheapest test of this exact boundary.

## The first person

The first person has nobody ahead, so their claim must be exactly 0. That falls out of the sweep with no special case, because the tally is empty and the count is 0.

## Cost

Time O(n log H). Space O(H) for the tree.

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ h ≤ 100000` - `0 ≤ k < n`