Минимум максимума

Задача:

Даны n нестрого возрастающих массивов Ai и m нестрого убывающих массивов Bj. Все массивы имеют одну и ту же длину
l. Далее даны q запросов вида (i,j), ответ на запрос – такое k, что max(Aik,Bjk) минимален. Если таких k несколько, можно вернуть любое.

Формат входных данных
На первой строке числа n,m,l (1≤n,m≤900;1≤ l≤3000). Следующие n строк содержат описания массивов Ai. Каждый массив описывается перечислением l элементов. Элементы массива – целые числа от 0 до 105−1. Далее число m и описание массивов Bj в таком же формате. Массивы и элементы внутри массива нумеруются с 1. На следюущей строке число запросов q (1≤q≤n⋅m). Следующие q строк содержат пары чисел i,j (1≤i≤n, 1≤j≤m).

Формат результата
Выведите q чисел от 1 до l – ответы на запросы.

Примеры
Входные данные
4 3 5
1 2 3 4 5
1 1 1 1 1
0 99999 99999 99999 99999
0 0 0 0 99999
5 4 3 2 1
99999 99999 99999 0 0
99999 99999 0 0 0
12
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
4 1
4 2
4 3
Результат работы
3
4
3
5
4
3
1
2
2
4
4
3

Есть два решения:

Первое в лоб, разумеется не проходит по времени

sp_A, sp_B, AB_max = [], [], []
n, m, l = list(map(int, input().split()))
for i in range(n):
A = list(map(int, input().split()))
sp_A.append(A)

for j in range(m):
B = list(map(int, input().split()))
sp_B.append(B)

q = int(input())
for p in range(q):
i, j = list(map(int, input().split()))
for u in range(l):
AB_max.append(max(sp_A[i-1][u], sp_B[j-1][u]))
print(AB_max.index(min(AB_max))+1)
AB_max = []


Второе чуть быстрее, но в 3 секунды всё равно не укладывается

sp_A, sp_B, AB_max = [], [], []

n, m, l = list(map(int, input().split()))

for i in range(n):
A = list(map(int, input().split()))
sp_A.append(A)

for j in range(m):
B = list(map(int, input().split()))
sp_B.append(B)

q = int(input())

for p in range(q):
i, j = list(map(int, input().split()))
AB_max.append(max(sp_A[i-1][0], sp_B[j-1][0]))
x = 1
for u in range(1, l):
AB_max.append(max(sp_A[i-1][u], sp_B[j-1][u]))
if AB_max[u] <= AB_max[u-1]:
x = x+1
else:
break
print(x)
AB_max = []

Как сделать так, чтобы используя бинарый поиск уложиться в отведённое время?

0

Ketlin_Morgan, а где ты используешь бин.поиск?

0

Не использую, в том и проблема. Его нужно использовать, но я не понимаю, где его здесь прикрутить, массив то не отсортирован.

Добавлено через 55 минут
eaa, есть идеи, как это можно осуществить?

0

вроде по примеру правильно:

0

eaa, не проходит при 3 1 и 4 1. Получается 5 и 3 вместо 1 и 4

0