1114. Counting the Weaker Fighters
Each fighter has an ATTACK and a DEFENCE. Fighter x is WEAKER when some other fighter
y beats them on both counts at once: attack[y] > attack[x] AND
defence[y] > defence[x], both strictly.
Print how many fighters are weaker.
(5,5) (6,3) (3,6) -> 0 nobody wins on both counts
(2,2) (3,3) (1,1) -> 2 only (3,3) survives
(1,5) (10,4) (4,3) (1,5) -> 1
(5,1) (5,2) (5,3) (4,1) -> 1
The last line is the interesting one. The three fighters with attack 5 never beat one
another, because equal attack is not strictly larger. Only (4,1) is weaker, beaten by
(5,2) and by (5,3).
## What most people try first
Comparing every pair, which is exactly right and costs O(n^2). At n = 200000 that
is 4 * 10^10 comparisons.
Sorting by attack descending and keeping a running maximum defence is the fast version,
and it is WRONG if the tie in attack is not handled, which is the whole content of this
problem. Sorting (5,1) (5,2) (5,3) (4,1) by attack descending in some arbitrary order
of the ties and sweeping a running maximum defence reports (5,1) and (5,2) as weaker
whenever (5,3) happens to come first, giving 3 instead of 1.
## The method
sort by attack DESCENDING, and for equal attack by defence ASCENDING
best = minus infinity
count = 0
for (attack, defence) in that order:
if defence < best: count = count + 1
best = max(best, defence)
One sort and one pass, O(n log n).
## Why the second sort key carries the whole thing
After the sort, everything seen before the current fighter has attack at least as large.
The running maximum best is the largest defence among them. So defence < best says
"somebody already seen has a strictly larger defence", and the question is whether that
somebody also has a strictly larger attack.
If the tie in attack is ordered by defence ASCENDING, then among fighters with the same
attack the defences arrive in increasing order, so best never exceeds the current
defence from within the same attack group. Any best strictly above the current defence
therefore came from a strictly larger attack, which is exactly the condition.
Reverse that second key and the group's own largest defence arrives first, and every later member of the group is falsely marked weaker.
The comparison is defence < best, strictly, for the same reason: equal defence is not
being beaten.
## Why nothing more clever is needed
This is not an exchange argument, it is a DOMINANCE sweep, and the useful thing to carry away is that a two-dimensional comparison collapses to one dimension once the other is sorted, provided the ties are handled so that the sorted dimension really is strictly ordered where it needs to be.
## Sizes
n reaches 2 * 10^5 and both statistics reach 10^5. The answer is at most n.
Nothing here is added or multiplied, so 32-bit arithmetic is enough everywhere.
## A related problem
Problem #1097 is the same move on intervals: sort by one endpoint and let a running maximum of the other decide containment, with the tie key doing the real work. The two problems are deliberately the same shape with different stories.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ attack ≤ 100000` - `1 ≤ defence ≤ 100000`
Input
The first line contains an integer n.
Each of the next n lines contains two integers, the attack and the defence of one fighter.
Output
Print one integer alone on a line: how many fighters are beaten on both attack and defence at once by some other fighter. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.