Library#213

Library (Editorial)

Задача розв'язується прямим моделюванням: достатньо в кожен момент часу знати, чи є конкретна книжка в бібліотеці.

Заведемо булевий масив , у якому означає, що книжка зараз наявна. Початково всі книжки на місці, тому масив заповнюємо значенням «так».

Далі обробляємо відвідувачів по порядку:

  • t = 1 (хоче взяти книжку ): якщо істинне, відвідувач забирає книжку і ми ставимо у «ні». Інакше книжки немає — збільшуємо лічильник невдоволених;

  • t = 2 (повертає книжку ): ставимо у «так».

Відповідь — значення лічильника після обробки всіх запитів.

Умова гарантує, що повертають лише раніше взяту книжку, тому додаткових перевірок для t = 2 не потрібно. Важливо, що кожна книжка існує в єдиному екземплярі, — саме тому вистачає булевого прапорця, а не лічильника.

Складність — \mathcal{O}(n + m), що при n \le 1000 і m \le 5000 працює миттєво.