Два варианта на выбор

Первый - красивый

Красиво можно решить вот так.

Создайте два массива L и R. В массиве L хранятся пары (l, n), где l - координата левого конца n-ного носка. В массиве R пары (r,n) - координата правого конца n-го носка. Оба массива отсортированы по возрастанию координаты.

Чтобы вычислить покрытие для точки с координатой x, находите все пары (l,n) из L, для которых l<=x, и все (r,n'), для которых x<=r. Общие номера n и n' - читай, пересечение множеств, - это номера тех носков, которые покрывают точку x.

Оценка сложности поиска общих номеров. Списки чисел n и n' нужно отсортировать - оценка 2N ln(N), потом найти в этих списках общие элементы - сложность порядка 2N, то есть суммарная сложность для M точек 2MN(ln(N)+1)

Второй - быстрый

с предварительной обработкой массива носков.

задача решается так: создаётся массив C целых чисел длиной L+1. Этот массив будет хранить покрытие для каждой точки. Вначале в каждом элементе массива значение 0 - нет ни одного носка, покрытие везде 0.

При добавлении очередного носка c координатами [l,r] инкрементируем C[i] для всех индексов от l до r

После того, как добавлены N носков, в массиве C толщина покрытия для каждой точки.

Если sock_len - средняя длина носка, то сложность алгоритма N sock_len по времени. От числа точек M вообще не зависит.

Если средняя длина носков невелика, sock_len < 2M(ln(N) + 1), то второй вариант быстрее первого. На самом деле это не совсем так, 2M(ln(N) + 1) - это верхняя граница, и фактическая сложность может быть гораздо меньше, но мне сейчас лень считать точнее

Это общее правило - тратим память для большей скорости.

Запрограммировать сможете?

Сверхскоростное решение

Решение можно придумать за O(L). Просто вместо прохода по всему массиву каждый раз при добавлении отрезка, мы будем добавлять в массив только начало и конец. (Полуинтервалом [) ). Если начало, то прибавляем единицу a[l] += 1, а если конец, то вычитаем ее a[r + 1] -= 1. Потом проходимся по этому массиву, и определяем уровень вложенности в любой точке. Решение без сортировки.

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

deltaArr = [0] * l
#Создаем массив изменений длинной l. Он нам поможет определить
#уровень вложенности в любой точке
#Если носок начался, уровень вложенности в i точке увеличился
#Если носок закончился, то уровень вложенности уменьшился
for i in range(n):
    left, right = map(int, input().split())
    left -= 1
    right -= 1
    deltaArr[left] += 1
    #добавляем носок полуинтервалом, т.к конец носка тоже должен учитываться
    #Мы можем выйти за границы массива, обязательно проверяем это
    if (right + 1 < l):
        deltaArr[right + 1] -= 1

#Создаем массив, i элемент которого будет содержать информацию о вложенности в i точке  
socks = [0] * l 

value = 0

for i in range (l):
    value += deltaArr[i]
    socks[i] = value

for i in range(m):
    point = int(input())
    print(socks[point - 1])

Тестируем...

31 12 4
19 20
1 3
9 26
8 31
15 26
15 20
5 20
17 27
21 23
2 24
10 19
1 27
15
23
28
23

Ответ:

8
7
1
7

Почему мы добавляем носок(отрезок) полуинтервалом? Потому что, правый конец носка, как и левый, тоже является его частью и закончится он тогда, когда закончится правый носок и начнется стол/другой носок

Вариант № 1, с использованием сортировки

Идея

1. Требуется узнать, сколько носков приходится на искомую точку M. Подходящим считается носок, начало которого <= M, конец которого >= M, другими словами, если заменить носок на отрезок, то точка M должна входить в этот отрезок.

2. Самый простой и медленный способ это перебрать все носки. Его можно усовершенствовать, отсортировав начала носков по возрастанию. Тогда перебор можно закончить, когда пошли отрезки (носки), которые начинаются после точки M. Тоже самое с концами носков - нет смысла проверять отрезки, заканчивающиеся раньше точки M. Тут поможет вторая сортировка - расположить концы по убыванию - как только пошли концы меньше точки M, проверку можно заканчивать.

Решение

def thickness_at_point(point, socks):
    cnt = 0
    # socks - отсортированный список.
    # Благодаря его отсортированности, можно завершать работу
    # как только пошли "начала" носков, превышающие требуемую точку
    for sock_start, sock_ends in socks:
        if point < sock_start:
            return cnt
        # Списки с концами тоже отсортированны, поэтому можно
        # завершать проверку при первом неподходящем значении, так как
        # известно, что остальные концы меньше или равны текущему,
        # соответствено также не подходят.
        for sock_end in sock_ends:
            if point > sock_end:
                break
            cnt += 1

    return cnt

desk_len, socks_num, points_num = map(int, input().split())

# Словарь нужен для оптимизации - складываем под одним ключом все носки с
# одинаковым началом. Концы этих носков добавляем в список, который хранится
# в значении данного ключа.
dct = {}
for _ in range(socks_num):
    start, end = map(int, input().split())
    dct.setdefault(start, [])
    dct[start].append(end)

# Переводим словарь в список содержащий кортеж вида: 
# (точка начала носка, [концы всех носков, стартующих с этого начала])
# Например, (5, [15, 10, 8, 7]) означает, что есть 4 носка,
# начинающихся в точке 5 и заканчивающихся в точках 15, 10, 8, 7.
# Список с концами должен быть отсортирован в обратном порядке
socks_lst = []
for start, ends in dct.items():
    socks_lst.append( (start, sorted(ends, reverse=True)))

# Сортируем список по "началам носков".
socks_lst.sort()

points_lst = [int(input()) for _ in range(points_num)]

for point in points_lst:
    print(thickness_at_point(point, socks_lst))

Вариант № 2, короткий и быстрый, но без использования сортировки

Идея взята из этого ответа.

desk_len, socks_num, points_num = map(int, input().split())

socks_lst = [0] * (desk_len + 2)

for _ in range(socks_num):
    start, end = map(int, input().split())
    socks_lst[start] += 1
    socks_lst[end + 1] -= 1

points_lst = [int(input()) for _ in range(points_num)]

for point in points_lst:
    print(sum(socks_lst[:point + 1]))

Тестирование обоих вариантов

Input

39 4 7 
3 21
3 15
3 17
2 20
4
17
33
5
9
25
37

Output

4
3
0
4
4
0
0