visual walkthrough
Successful Pairs of Spells and Potions
MediumSort + Binary Search
Sort once, then binary search per query.
The idea
For one spell, a potion works if it's at least ⌈success / spell⌉. After sorting, those potions sit together at the end.
So each spell needs one binary search for where that block starts, and the count is everything from there.
Complexity
| approach | time | space |
|---|---|---|
| Every pair | O(n · m) | O(1) |
| Sort + binary search | O((n + m) log m) | O(m) |