Hunter In Jury#12829

Hunter In Jury (Editorial)

Олег Валлас

Спочатку покажемо, що порядок, в якому ми випускаємо стріли, не впливає на результат. Для цього розглянемо політ 2х стріл. Якщо їх траєкторії не перетинаються, тоді очевидно, що їх можна випускати в будь-якому порядку. Якщо ж вони перетинаються, то зміна порядку просто поміняє їх місцями в точці перетину, в той час як множина збитих кульок не зміниться. Дивіться малюнок для кращого розуміння.

Використовуючи цю властивість можна запускати всі стріли паралельно. Будемо обробляти кульки зліва направо і підтримувати масив cnt на мільйон елементів, де означатиме кількість стріл, які летять на висоті . Спочатку заповнимо масив нулями. Коли ми зустрічаємо чергову кульку на висоті , перевіримо чи є у нас якась стріла на висоті . Якщо немає, то необхідно додати нову і збільшити відповідь (cnt[h]++; answer++;). Після цього кульку можна збити будь-якою стрілою на висоті (пам'ятаємо, що порядок стріл не важливий), а саме — зробити «cnt[h]—; cnt[h - 1]++;». В кінці просто виведемо змінну .

Складність O(N + H) часу, та пам'яті, де — кількість кульок, а — максимальна висота кульки, що в рамках задачі дорівнює 10^6.