Районная олимпиада 2019-2020 информатика
Задача C. Ресторан
В ресторане есть $n$ официантов. Они пронумерованы от $1$-го до $n$. На столе стоят $m$ стаканов. Они пронумерованы от $1$-го до $m$. Изначально все стаканы пустые. Каждый официант должен налить напиток в некоторые стаканы. $i$-й официант должен налить в стаканы с номерами от $l_i$ до $r_i$ по $x_i$ миллилитров напитка. Какой-то официант проспал и забыл сделать это. Все остальные кроме него выполнили задание. Вам дано количество миллилитров напитка в каждом стакане. Нужно найти список, тех официантов, кто возможно проспал.
- $1 <= n, m <= 100$. Тесты с номерами 1-2.
- $1 <= n, m <= 3000$. Тесты с номерами 3-5.
- $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 )
Комментарий/решение:
С новым годом. Не проходит по времяни в 6 том тесте. Буду благодарен, если найдете другие варианты решение. :)
В своем решение вы полностью проходите по отрезку [l, r]. Это решение будет работать но так как вы делаете это 10^5 раз итоговая асимптотика выходит O(nm), что очень медленно. Задача решается с помощью дерева отрезков или же так как задача без обновлений, то есть офлайн можно итоговый массив получить вот так:
При каждом считывании l, r, x в дополнительном массиве на индексе l добавьте x, в индексе r + 1 отнимите x. Затем поступите префикс сумму по этому массиву и это будет итоговый массив.
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)
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.