Loading [MathJax]/jax/output/SVG/jax.js

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


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

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

В ресторане есть n официантов. Они пронумерованы от 1-го до n. На столе стоят m стаканов. Они пронумерованы от 1-го до m. Изначально все стаканы пустые. Каждый официант должен налить напиток в некоторые стаканы. i-й официант должен налить в стаканы с номерами от li до ri по xi миллилитров напитка. Какой-то официант проспал и забыл сделать это. Все остальные кроме него выполнили задание. Вам дано количество миллилитров напитка в каждом стакане. Нужно найти список, тех официантов, кто возможно проспал.
Формат входного файла
В первой строке дается два целых числа n и m (1<=n,m<=105) — количество официантов и количество стаканов. В следующих n строках заданы по три целых числа li, ri и xi (1<=li<=ri<=m, 1<=xi<=103). В следующей строке заданы m целых числа a1, a2, , am, где ai обозначает количество миллилитров напитка в i-м стакане.
Формат выходного файла
Выведите номера в отсортированном порядке, тех официантов, кто возможно проспал.
Система оценки
Данная задача содержит 10 тестов. Каждый тест оценивается в 10 баллов:
  1. 1<=n,m<=100. Тесты с номерами 1-2.
  2. 1<=n,m<=3000. Тесты с номерами 3-5.
  3. 1<=n,m<=105. Тесты с номерами 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
5 года 3 месяца назад #

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

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

C++

  3
5 года 3 месяца назад #

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

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

пред. Правка 2   -1
4 года 4 месяца назад #

  0
4 года 4 месяца назад #

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

C++

  0
4 года 3 месяца назад #

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
3 года 1 месяца назад #

...

  0
3 года 1 месяца назад #

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

C++