Подзадача 1. 10 точки:

За 10 точки решението е просто два вложени цикъла по началата на двете реклами
в минути и трети вложен цикъл по клиентите, който брои колко клиента чуват
рекламите.

Забележете, че е е позволено рекламите да звучат извън времената, когато има
посетители в магазина. Затова разглеждаме начала на реклами между -M и max B_i.

Сложност: O((MAX_M + MAX_AB)^2 * N)

Подзадача 2. 20 точки:

Тук решението е със същата идея, но трябва да разглеждаме само "релевантните"
минути. Да си представим, че първата реклама започва в минута K_1, но няма
посетител, който влиза в магазина в тази минута. Следва, че можем да пуснем
първата реклама и в K_1 без да влошим отговора. Т.е. първата реклама винаги започва
в минута, в която влиза нов клиент. Аналогично, втората реклама винаги свършва
в минута, в която излиза клиент, т.е. започва M минути преди това.

Така можем да разглеждаме за начала на рекламите само 2N минути. Отново обаче
трябва да позволим начало в минута -M (извън работно време). Това е важно, когато
няма време и двете реклами да бъдат чути от клиенти например.

Сложност: O(N^3)

Подзадача 3. 40 точки:

В предното решение броим броя клиенти чули рекламите в най-вътрешния цикъл.
Правим това по O(N) пъти за всяко възможно начало на реклама. По-добре е за
всяко възможно начало, да преброим броя клиенти, които изцяло биха чули реклама
пусната тогава, и после да използваме тези precompute-нати стойности вместо
трети вложен цикъл.

Сложност: O(N^2)

Подзадача 4. 20 (+ 40) точки:

Решението за рази подзадача вече е доста близко до пълното, но разглежда частен
случай, когато рекламите са точки във времето, което опростява някои стъпки.

Както преди, намираме списък от всички релевантни минути, но после ги сортираме.
След това ги обхождаме и за всяка от тях искаме да намерим колко клиенти са в
магазина по време на съответната минута. Правим това като държим пойнтъри към
последното A (минута на влизане) и последното B (минута на излизане) преди
текущата минута. На всяка стъпка ги ъпдейтваме като ги движим надясно през
съответните им масиви (които също сме сортирали в началото). Бройката клиенти
в магазина в текущата минута е просто: бройката, които вече са влезли, - бройката,
които вече са излезли.

След като имаме бройките клиенти в магазина във всяка релеванта минута, просто
итерираме през тях и следим префиксния максимум. Така на всяка стъпка
prefMaxCnt[i] + cnt[i + 1] е оптималния отговор, ако втората реклама започва в
(i + 1)-вата минута. Крайният отговор е максимумът от тези отговори.

Сложност: O(N log N)

Подзадача 4. 100 точки:

Тук отново имаме същите три стъпки:
1. Намираме релевантните минути и ги сортираме.
2. Намираме броя хора, които биха чули реклама започваща във всяка от тези минути.
3. Намираме отговора.

Стъпка 2. е подобна, но пойнтърът към B трябва да сочи M минути напред. Тук обаче
има проблем, че можем да подценим отговора. Това е защото може клиент да бъде
отчетен от B пойнтъра, но все още да не е отчетен от A пойнтъра. Това се случва,
когато клиентът стои под M минути в магазина. Но това е лесно за оправяне, като
изцяло премахнем тези клиенти, което е допустимо, защото те никога не биха чули
цяла реклама.

С цел ефикасност тази стъпка е имплементирана по малко по различен начин в пълното
решение. Вместо следене на пойнтъри, просто анотираме всяка релевантна минута с
това дали е влизане или излизане (или изкуствената -M минута). После следим броя
хора в магазина по време на текущата реклама използвайки само анотациите на
релевантните минути (т.е. няма нужда да соритраме A и B масивите).

За стъпка 3. вече не можем да гледаме просто i и i + 1, защото тези две минути
може да са на разстояние под M една от друга (което не е възможно в подзадача 4,
когато M = 1). Това е лесно за коригиране, като следим i и j, където j е
пойнтър към най-малката релевантна минута, която е поне M след минута i.
Също така, предварително си пресмятаме суфиксните максимуми (суфиксни, а не
префиксни, защото i ще посети всяка релевантна минута, но това не важи за j).
Текущият отговор на дадена стъпка е cnt[i] + suffMaxCnt[j], а крайният отговор
отново е максимумът на тези текущи отговори.

Сложност: O(N log N)

Идея и условие: Павел Николов
Имплементация: Емил Инджев