Выбор алгоритма для задачи

def answer_queries(sorted_values, queries):
    result = []
    for x in queries:
        result.append(count_elements_less_than(sorted_values, x))
    return result

# len(sorted_values) = 200_000
# len(queries) = 100_000

def longest_segment(a, limit):
    best = 0
    for left in range(len(a)):
        total = 0
        for right in range(left, len(a)):
            total += a[right]
            if total <= limit:
                best = max(best, right - left + 1)
    return best

# Все элементы a положительны.

graph = {
    'сборка': ['тесты'],
    'тесты': ['публикация'],
    'документация': ['публикация'],
    'публикация': [],
}

# Нужно получить порядок, в котором каждая вершина
# расположена после всех входящих в неё зависимостей.

def count_inversions(a):
    count = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] > a[j]:
                count += 1
    return count

n = 200_000

V = 100_000
E = 200_000

matrix_cells = V * V
adjacency_entries = 2 * E
visited_entries = V
queue_capacity = V

print(matrix_cells, adjacency_entries,
      visited_entries, queue_capacity)
# Нужно выбрать представление, которое не помещается в разумную память.

def answer_queries(a, queries):
    answers = []
    for left, right in queries:
        answers.append(min(a[left:right + 1]))
    return answers

# a не меняется, запросов около 1_000_000.

events = []

def add_event(timestamp, payload):
    events.append((timestamp, payload))

def take_nearest():
    index = min(range(len(events)), key=lambda i: events[i][0])
    return events.pop(index)

# Обе операции выполняются постоянно.

def window_maximums(a, k):
    result = []
    for left in range(len(a) - k + 1):
        result.append(max(a[left:left + k]))
    return result

# Нужно снизить суммарную сложность до O(n).

while items:
    x = items.pop(0)
    process(x)

for case in random_small_cases():
    fast = solve_fast(case)
    slow = solve_bruteforce(case)
    assert fast == slow

def maximum(a):
    best = 0
    for x in a:
        best = max(best, x)
    return best

a = [10, 1, 7]
x = 10
# mid=1, a[mid]=1 < 10, поиск отбрасывает левую половину