@YSSITJ

Можете пожалуйста помочь с решением задач?

ПЫТАЮСЬ(ключевое слово) решить задачи -> https://contest.yandex.ru/contest/50668/problems/D...
данного контеста, но возникают проблемы. Есть ли у кого нибудь ответы на этот контест?
И не могли бы вы проверить почему мой код проходит по тестам, кроме тайм лимита(примерно понимаю что уровень O(N^2), но не знаю как упростить). Задача D "Лей, лей, не жалей"
a = [list(map(int, input().split())) for _ in range(int(input()))]
for i in range(int(input())):
    s = 0
    rs, re, typ = map(int, input().split())
    for st, end, cost in a:
        if typ == 1 and re >= st >= rs:
            s += cost
        elif typ == 2 and rs <= end <= re:
            s += end - st
    print(s, end=' ')
  • Вопрос задан
  • 151 просмотр
Решения вопроса 1
LaRN
@LaRN
Senior Developer
Если упопядочить данные в списке "а" по возрастанию диапазонов, то не нужно будет всякий раз бежать до конца списка.
Можно будет сразу сделать break как только st и end перестанут укладываться в диапазон rs-re.
Опять же при наличии сортировки можно попообовать использовать бинарный поиск.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы