2025: [USACO 2024 February Contest Bronze] Problem 3. Maximizing Productivity

Farmer John has $N$ ($1\le N\le 2\cdot {10}^5$) farms, numbered from $1$ to $N$. It is known that FJ closes farm $i$ at time $c_i$. Bessie wakes up at time $S$, and wants to maximize the productivity of her day by visiting as many farms as possible before they close. She plans to visit farm $i$ on time $t_i+S$. Bessie must arrive at a farm strictly before Farmer John closes it to actually visit it.

Bessie has $Q$ $(1\le Q\le 2\cdot {10}^5)$ queries. For each query, she gives you two integers $S$ and $V$. For each query, output whether Bessie can visit at least $V$ farms if she wakes up at time $S$.

The second line consists of $c_1,c_2,c_3\dots c_N$ ($1\le c_i\le {10}^6$).

The third line consists of $t_1,t_2,t_3\dots t_N$ ($1\le t_i\le {10}^6$).

The next $Q$ lines each consist of two integers $V$ ($1\le V\le N$) and $S$ ($1\le S\le {10}^6$).

5 5
3 5 7 9 12
4 2 3 3 8
1 5
1 6
3 3
4 2
5 1

YES
NO
YES
YES
NO