I Don't Like Summer

この問題では、$A$ を昇順にソートし、forループなどを用いて $X < A_i$ を満たす $i$ を線形探索することにより、各質問に $O(N)$ で答えることができます。

しかし、このような愚直なアルゴリズムでは、計算時間が $O(NQ)$ となってしまい、この制約下では実行時間制限に間に合いません。

そこで、各質問に対して高速に答えることでこの問題を AC することができました。

具体的には、昇順にソートした $A$ に対して、二分探索を利用すると $O(log \ N)$ 、
降順にソートした $A$ に対して $A_k < x$ となるかを判定すると $O(1)$ で各質問に答えることができます。

Python, bisectによる実装例

xxxxxxxxxx

from bisect import bisect

​

n = int(input())

a = list(map(int,input().split()))

q = int(input())

​

a = sorted(a)

​

for i in range(q):

    x,k = map(int,input().split())

    if n - bisect(a, x) + 1 <= k:

        print("Yes")

    else:

        print("No")