Районная олимпиада 2019-2020 информатика


Задача C. Ресторан

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

В ресторане есть $n$ официантов. Они пронумерованы от $1$-го до $n$. На столе стоят $m$ стаканов. Они пронумерованы от $1$-го до $m$. Изначально все стаканы пустые. Каждый официант должен налить напиток в некоторые стаканы. $i$-й официант должен налить в стаканы с номерами от $l_i$ до $r_i$ по $x_i$ миллилитров напитка. Какой-то официант проспал и забыл сделать это. Все остальные кроме него выполнили задание. Вам дано количество миллилитров напитка в каждом стакане. Нужно найти список, тех официантов, кто возможно проспал.
Формат входного файла
В первой строке дается два целых числа $n$ и $m$ $(1 <= n, m <= 10^5)$ — количество официантов и количество стаканов. В следующих $n$ строках заданы по три целых числа $l_i$, $r_i$ и $x_i$ $(1 <= l_i <= r_i <= m$, $1 <= x_i <= 10^3)$. В следующей строке заданы $m$ целых числа $a_1$, $a_2$, $\dots$, $a_m$, где $a_i$ обозначает количество миллилитров напитка в $i$-м стакане.
Формат выходного файла
Выведите номера в отсортированном порядке, тех официантов, кто возможно проспал.
Система оценки
Данная задача содержит $10$ тестов. Каждый тест оценивается в $10$ баллов:
  1. $1 <= n, m <= 100$. Тесты с номерами 1-2.
  2. $1 <= n, m <= 3000$. Тесты с номерами 3-5.
  3. $1 <= n, m <= 10^5$. Тесты с номерами 6-10.
Пример:
Вход
5 4
1 3 2
2 4 3
1 3 2
3 4 1
3 3 1
2 5 7 4
Ответ
1 3
( Aibar Kuanyshbay )
посмотреть в олимпиаде

Комментарий/решение:

  0
2020-01-01 14:02:53.0 #

С новым годом. Не проходит по времяни в 6 том тесте. Буду благодарен, если найдете другие варианты решение. :)

показать/скрыть код

  3
2020-01-02 04:52:37.0 #

В своем решение вы полностью проходите по отрезку [l, r]. Это решение будет работать но так как вы делаете это 10^5 раз итоговая асимптотика выходит O(nm), что очень медленно. Задача решается с помощью дерева отрезков или же так как задача без обновлений, то есть офлайн можно итоговый массив получить вот так:

При каждом считывании l, r, x в дополнительном массиве на индексе l добавьте x, в индексе r + 1 отнимите x. Затем поступите префикс сумму по этому массиву и это будет итоговый массив.

пред. Правка 2   -1
2020-12-02 19:56:44.0 #

  0
2020-11-28 10:28:37.0 #

показать/скрыть код

  0
2020-12-19 22:45:21.0 #

n, m = input().split()

n, m = int(n), int(m)

lrx = [[]for i in range(n)]

for i in range(n):

lrx[i] = input().split()

for j in range(3):

lrx[i][j] = int(lrx[i][j])

a= input().split()

for i in range(len(a)):

a[i] = int(a[i])

a_full = [0]*m

for i in range(n):

l=lrx[i][0]

r=lrx[i][1]

x=lrx[i][2]

for j in range(l-1,r):

a_full[j]+=x

mistake = [0]*3

l = float('inf')

for i in range(m):

if a[i] != a_full[i]:

mistake[2] = a_full[i]-a[i]

if i<l:

mistake[0] = l = i+1

mistake[1]= i+1

maybe=[]

for i in range(n):

if lrx[i][0] == mistake[0] and lrx[i][1] == mistake[1] and lrx [i][2] == mistake[2]:

maybe.append(i+1)

for i in maybe:

print(i)

пред. Правка 3   0
2022-02-08 13:19:12.0 #

...

  0
2022-02-08 12:35:33.0 #

показать/скрыть код