公式解説とは異なる方針の解法を解説します。計算量は \(O(N\log N+Q\log Q)\) です。

身長だけでなく、クエリもソートすることで、クエリで問われる値は徐々に小さくなるとして良いです。このとき、尺取法の要領で、クエリ全体に \(O(N)\) で答えることができます。

実装例(Python)
※ \(A\) と \(X\) をまとめてソートしているため、計算量は \(O((N+Q)\log(N+Q))\)

このように、全てのクエリを先に受け取り都合の良い順序に並び替えてから答える手法は、高難易度の問題を解く際にしばしば使われます。