Subtask 1: $N, Q < 10^3$.

We can directly simulate the process according to the problem statement. For each query, we iterate through all the farms and see if we can visit it in time, $t_i + S < c_i$. Each query takes $\mathcal{O}(N)$ operations, giving us an $\mathcal{O}(NQ)$ solution.

Alex Fan's C++ Code:

using namespace std;

#include <iostream>

#define MAXN 200005

int N,Q,c[MAXN],t[MAXN];

int main() {
	cin >> N >> Q;
	for(int i = 0;i < N;++i) {
		cin >> c[i];
	}
	for(int i = 0;i < N;++i) {
		cin >> t[i];
	}

	for(int i = 0;i < Q;++i) {
		int v,s;
		cin >> v >> s;
		int uwu = 0;
		for(int j = 0;j < N;++j) {
			if(s + t[j] < c[j]) {
				uwu++;
			}
		}
		cout << (uwu >= v ? "YES" : "NO") << endl;
	}

	return 0;
}

Python Code:

N, Q = (int(x) for x in input().split())
c = [int(x) for x in input().split()]
t = [int(x) for x in input().split()]
for _ in range(Q):
    V, S = (int(x) for x in input().split())
    uwu = 0
    for i in range(N):
        if(S + t[i] < c[i]):
            uwu += 1
    print("YES" if (uwu >= V) else "NO")

Subtask 2: $c_i, t_i < 20$

The key observation is to notice that we can rearrange the formula $t_i + S < c_i$ as $c_i - t_i > S$. Therefore, for each farm, we can take advantage of the fact that $c_i - t_i$ can only be between $-20$ to $20$.

If $c_i - t_i \leq 0$, then we can get rid of it since we can never make it in time. Otherwise, there are only $21$ possible values despite there being $2 \cdot 10^5$ farms. We exploit this observation by grouping the same $c_i - t_i$ values together. This can be implemented with a map, or, since the values are between $0$ and $20$, an array of length $21$.

Finally, to check if a query works, we iterate through the array and count the number of valid barns that satisfy the inequality. The valid range is always the continuous interval to the right of $S$.

Each query takes $\mathcal{O}(MAXC)$ time where $MAXC \leq 20$ is the maximum value of $c_i$, so the total complexity is $\mathcal{O}(N + Q \cdot MAXC)$

Alex Fan's C++ Code:

using namespace std;

#include <iostream>
#include <map>

#define MAXN 200005
#define MAXA 1000005

int N,Q,c[MAXN],t[MAXN],cnt[MAXA],max_element;

int main() {
	cin >> N >> Q;
	for(int i = 0;i < N;++i) {
		cin >> c[i];
	}
	for(int i = 0;i < N;++i) {
		cin >> t[i];
		if(c[i] > t[i]) {
			// Maintain the count array of c[i] - t[i]
			cnt[c[i] - t[i]]++;
		}
		// We can also replace max_element as the constant 20
		max_element = max(max_element,c[i] - t[i]);
	}

	for(int i = 0;i < Q;++i) {
		int v,s;
		cin >> v >> s;
		int uwu = 0;
		if(N <= 1e3) {
			// Subtask 1
			for(int i = 0;i < N;++i) {
				if(t[i] + s < c[i]) uwu++;
			}
		}else if(max_element <= 20) {
			// Subatsk 2
			for(int i = s + 1;i <= max_element;++i) {
				uwu += cnt[i];
			}
		}
		cout << (uwu >= v ? "YES" : "NO") << endl;
	}

	return 0;
}

Python Code:

N, Q = (int(x) for x in input().split())
c = [int(x) for x in input().split()]
t = [int(x) for x in input().split()]

cnt = [0] * 25

for i in range(N):
	if(c[i] > t[i]):
		cnt[c[i] - t[i]] += 1

for _ in range(Q):
    V, S = (int(x) for x in input().split())
    uwu = 0
    for i in range(S + 1,25,1):
        uwu += cnt[i]
    print("YES" if (uwu >= V) else "NO")

Full Credit:

The final step is to efficiently count the number of farms such that their $c_i - t_i$ is greater than some query value $S$. This is a standard setup that can be solved by first sorting all the differences and applying binary search. This gives an $\mathcal{O}(N\log N + Q\log N)$ solution.

Alternatively, you can further observe that after we sort all the values of $c_i - t_i$, the query $(V, S)$ is "YES" if and only if the $V$-th largest value of $c_i - t_i$ is more than $S$, which can be done by checking the $i$-th element of the sorted array. Reference Brandon Wang's Python Code for the implementation. This also results in a $\mathcal{O}(N\log N + Q)$ solution.

Alex Fan's C++ Code:

using namespace std;

#include <iostream>
#include <algorithm>
#include <fstream>

#define MAXN 200005

int N,Q,c[MAXN],t[MAXN];

int main() {
	cin >> N >> Q;
	for(int i = 0;i < N;++i) {
		cin >> c[i];
	}
	for(int i = 0;i < N;++i) {
		cin >> t[i];
		c[i] -= t[i];
	}

	sort(c,c + N);

	for(int i = 0;i < Q;++i) {
		int v,s;
		cin >> v >> s;
		int uwu = N - (lower_bound(c,c + N,s + 1) - c);
		cout << (uwu >= v ? "YES" : "NO") << endl;
	}

	return 0;
}

Brandon Wang's Python Code

N, Q = (int(x) for x in input().split())
c = [int(x) for x in input().split()]
t = [int(x) for x in input().split()]
diffs = sorted([ci - ti for ci, ti in zip(c, t)], reverse=True)
for _ in range(Q):
    V, S = (int(x) for x in input().split())
    print("YES" if (V <= N and (V <= 0 or diffs[V-1] > S)) else "NO")