Зеник з \(i\)-ої гвинтівки може вистрілити \(\lfloor \frac{x}{b_i} \rfloor + 1\) разів. Тому нам необхідно помножити це число на \(a_i\), щоб порахувати шкоду, що може нанести \(i\)-а гвинтівка. Отже, в задачі необхідно знайти гвинтівку з найбільшим таким значенням.
Для того аби знищити \(i\)-тий
ворожий літак Зенику необхідно нанести \(\lceil \frac{h_i}{a} \rceil\) ударів. І щоб
Зеника не підбили його літак повинен витримати вистріли у відповідь,
таких вистрілів буде \(\lceil \frac{h_i}{a}
\rceil - 1\). А сумарна шкода літаку Зеника за цей двобій буде
рівна \((\lceil \frac{h_i}{a} \rceil - 1)
\cdot d_i\). Отже, будемо пам’ятати скільки міцності в літака
Зеника ще залишилось і будемо віднімати сумарну шкоду. Якщо після
якогось повітряного бою в нього вийшла міцність менша або рівна за 0,
тоді літак Зеника не зможе вціліти і відповідь тоді No. А
якщо ж такого не сталось, то його літак цілий і у відповідь необхідно
вивести Yes.
Використаємо жадібний підхід. Для взводів, що мають однакову найменшу кількість людей, дамо по одному ящику з боєприпасами. Для взводів з другим найменшим значенням дамо по 2 ящики з боєприпасами і так далі. Тобто впорядкуємо взводи за кількістю людей в них. Перший з них отримає 1 ящик з боєприпасами. Далі ітеруємось по взводах від другого, якщо в даного взводу така ж кількість людей як в попереднього то дамо йому стільки ж якщиків як і попередньому взводу. Інакше необхідно дати на 1 ящик більше.
Зауважте, що відповідь може бути більшою за \(5 \cdot 10^9\), а отже необхідно використовувати тип даних, що дозволяє працювати з такими великими значеннями.
У нас є два варіанти в яку сторону буде відправлена посилка: вліво або вправо. Розглянемо випадок, коли посилка буде відправлена вправо (\(a_i < b_i\)). Інший варіант буде аналогічно розв’язуватись. Отже, для того аби доставити таку посилку ми маємо спочатку відвідати позицію \(a_i\), а потім \(b_i\). Припустимо, що ми можемо доставити певним чином посилку, тоді розглянемо останній раз коли ми були в клітинці \(a_i\) перед тим як доставити посилку. Ми повинні іти вправо з цієї клітинки, тобто мала існувати така ключова позиція \(x_j\), що існує наступна позиція \(x_{j+1}\) і виконується нерівність \(x_j \le a_i < x_{j+1}\). Аналогічно зробимо для \(b_i\), але ми розглянемо перше відвідування \(b_i\) після того як взяли посилку в \(a_i\). Тоді ми мали прийти в позицію \(b_i\) зліва, тобто має існувати такий момент \(x_k\) для якого існує \(x_{k-1}\) і виконується нерівність \(x_{k-1} < b_i \le x_k\). Отже, якщо існують два таких індекси \(j\) та \(k\) для яких виконується \(x_j \le a_i\), \(b_i \le x_k\) та \(j < k\) — умови того, що ми з \(a_i\) підемо вправо, в \(b_i\) прийдемо зліва і відповідно що посилку ми візьмемо швидше ніж доставимо її. Якщо таких індексів не існує, то ми не зможемо доставити посилку. У випадку якщо \(b_i < a_i\) нам потрібно знайти індекси \(j\) та \(k\) для яких виконуються умови \(a_i \le x_j\), \(x_k \le b_i\) та \(j < k\).
Для того аби перевірити чи існують потрібні індекси знайдемо найменше \(j\) для якого буде виконуватись умова між \(a_i\) та \(x_j\) (\(x_j \le a_i\) або \(a_i \le x_j\)). Аналогічно знайдемо найбільше \(k\) для якого буде виконуватись умова між \(b_i\) та \(x_k\) (\(b_i \le x_k\) або \(x_k \le b_i\)). Якщо відповідні індекси існують і для них виконується \(j < k\), тоді посилку можна доставити. Отже, такий розв’язок буде працювати за \(O(m \cdot n)\), бо для кожної посилки нам потрібно перебрати індекс ключової позиції.
Для пришвидшення попереднього розв’язку посортуємо \(n\) пар (\(x_{ind}\), \(ind\)), тоді кожна умова буде виконуватись для певного префіксу або суфіксу цього масиву. Оскільки нам потрібно мінімум і максимум, то створимо масив в якому будемо пам’ятати, на кожному префіксі та кожному суфіксі, мінімальне та максимальне значення другого параметру з пари. А визначати для якого префіксу або суфіксу виконується умова, можна за допомогою двійкового пошуку.
Для зручності відсортуємо вантажівки по їх координаті.
Для того аби отримати бали за два найлегших блоки необхідно було перебрати вантажівку в яку ми вистрілимо і відтворити процес вибухів. Наприклад, для цього можна підтримувати проміжок \([l, r]\), де усі вантажівки в цьому проміжку вибухнуть. Проте на цьому проміжку могли бути вантажівки які ми ще не розглянули, такі вантажівки можуть оновити значення \(l\) і \(r\). У простішому блоці можна було проітеруватись по усіх вантажівках і подивитись чи вони в проміжку і ми їх ще не розглнули. Для другого блоку процес пошуку не розглянутих вантажівок необхідно пришвидшити. Наприклад, можна пам’ятати впорадковану множину або використати метод двох вказівників
Для того аби розв’язати задачу зауважимо, що якщо відрізок вибуху вантажівки \([a_j - b_j, a_j + b_j]\) є вкладений у відрізок вибуху іншої вантажівки \([a_i - b_i, a_i + b_i]\), тоді нам не вигідно стріляти в \(j\)-ту вантажівку, бо \(i\)-та підірве не менше вантажівок. Якщо ми не будемо пробувати підривати такі вантажівки як \(j\)-та, тоді вибух буде поширюватись незалежно вліво та вправо. Тобто, якщо ми детонацією зачепимо вантажівку справа, то вибух від неї пошириться не лівіше ніж був до того. А отже, ми маємо окремо порахувати скільки вантажівок ми підірвемо зліва і скільки справа, якщо вибухи незалежні. Тобто, вибухи \(i\)-ї вантажівки відбуваються у проміжку \([a_i - b_i, a_i]\) та \([a_i, a_i + b_i]\), відповідно для вибухової хвилі вліво і вправо. Для розвязання таких підзадач використаємо підхід динамічного програмування. Нехай \(L[i]\) — номер найлівішої вантажівки що ми можемо підірвати вибуховою хвилею вліво, якщо \(i\)-та вибухне. Аналогічно \(R[i]\) — номер найправішої вантажівки у випадку вибуховою хвилею вправо. Щоб обрахувати \(L[i]\) нам необхідно знайти найменше значення \(L[j]\) для якого виконується \(a_i - b_i \le a_j \le a_i\). Аналогічно, щоб обрахувати \(R[i]\) нам необхідно знайти найбільше значення \(R[j]\) для якого виконується \(a_i \le a_j \le a_i + b_i\). Такі значення можна знайти за допомогою структур даних, які вміють шукати мінімум на відрізку, і змінювати значення в точці. Наприклад, можна використати дерево відрізків. Маючи такі значення, ми знаємо, що підірвавши \(i\)-ту вантажівку, відповідь буде \(R[i] - L[i] + 1\). Відповіддю на задачу буде максимум з таких значень.
Зауважимо, що якщо вибухи не можна розглядати незалежно, тобто для вантажівок, вибухова хвиля яких є вкладеною, то значення \(R[i] - L[i] + 1\) може бути меншим ніж кількість вантажівок, які вибухнуть якщо першою підірвати \(i\)-ту. Проте, ми показали, що в такі вантажівки стріляти неоптимально, а це означає, що ми можемо проігнорувати це.
Перш за все в цій задачі необхідно було зрозуміти, що в нас задано кореневе дерево. Тоді дороги з даної вершини до вершин східніше це теж саме, що й ребра до синів в дереві. Отже, наш запит перетворюється у такий: порахуйте суму вершин в піддереві вершини \(v_i\) на відстані не більше \(d_i\).
Тоді для зручності порахуємо \(h[i]\) — глибину \(i\)-ї вершини, тобто відстань до кореня дерева. Для цього напишемо, наприклад, обхід в глибину. Тоді вершини в піддереві будуть мати глибину більшу ніж в кореня піддерева. А відстань від вершини до її предка рівна різниці їх глибин. А, отже, для того аби отримати бали за перший блок тестів достатньо було написати обхід дерева починаючи з вершини \(v_i\) і йдучи у вершини з більшою глибиною. І під час цього процесу додавати до відповіді значення вершини якщо вона має глибину не більшу за \(h[v_i] + d_i\). Такий розв’язок буде мати складність \(O(q \cdot n)\).
Для другого блоку тестів потрібно було помітити, що відстань від поточної вершини до усіх інших завжди менша за \(n\). Тоді наша задача перетворюється до того, що нам необхідно порахувати суму в піддереві. Що можна було зробити в обході де ми обраховуємо \(h[i]\) і запам’ятати в масиві \(sum\).
Тепер для блоку без обмежень необхідно помітити, що ми можемо додати значення \(sum[v_i]\) і нам потрібно буде відняти значення \(sum\) для вершин в піддереві на глибині \(h[v_i] + d_i + 1\). Бо вершини на такій глибині не мають бути враховані у відповідь і їхні піддерева теж, оскільки в них глибина ще більша. Якщо ми в початковому обході в глибину будемо додавати вершину в список вершин на такій глибині. Тоді для будь-якої вершини, усі вершини в її піддереві на певній глибині будуть іти підряд у списку для цієї глибини. А отже, нам необхідно знайти проміжок вершин на глибині \(h[v_i] + d_i + 1\), що належать піддереву вершини \(v_i\) і порахувати їх суму. Порахувати суму можна використавши префіксні суми, бо у нас немає ніяких змін.
Підзадача з пошуком меж проміжку є складнішою, для того аби її розв’язати запам’ятаємо Ейлерів обхід дерева. Це можна зробити в нашому початковому обході в глибину, запам’ятавши для вершини \(tin\) та \(tout\) — часи коли ми увійшли та вийшли з вершини. Знаючи такі значення ми можемо сказати чи вершина \(u\) є строго у піддереві вершини \(v\) просто перевіривши \(tin[v] < tin[u] < tout[u] < tout[v]\). Тепер ми можемо для глибини рахувати не список вершин, а список значень \(tin\) для цих вершин. Тоді такий список буде посортований, оскільки ми додаємо вершини в тому порядку, в якому їх відвідували. У такому списку нам потрібно знайти \(l\) — індекс найлівішої вершини на рівні, яка є в піддереві вершини \(v\). Тобто таку \(u\), в якої мінімальний \(tin[u] > tin[v]\). Також нам потрібно знайти такий \(r\) — індекс найправішої вершини на рівні, яка є в піддереві вершини \(v\). Тобто таку \(u\), в якої максимальний \(tin[u] < tout[v]\). Це будуть межі відрізка, суму на якому нам потрібно відняти. Щоб знайти такі межі ми можемо використати двійковий пошук по часах входу на відповідному рівні.
Перш за все у задачі потрібно було помітити те, що радіус \(R\) можна шукати двійковим пошуком. Оскільки збільшивши радіус кола ділянка ураження тільки збільшиться і не може втратити зв’язність. Тепер для радіусу \(R\) потрібно перевірити чи можна розташувати три кола такого радіусу щоб покрити 3 задані точки і щоб усі кола були з’єднані.
Тоді у нас є два випадки: кожне коло містить точку або одне з кіл містить дві точки. Випадок, коли одне коло може містити 3 точки можна не розглядати, так як ми могли посунути це коло до того моменту коли одна з точок стане ззовні. Тоді помістити її в інше коло і отримати таку ж ситуацію як у другому випадку.
Розглянемо перший випадок, кожна точка буде знаходитись в окремому колі. Тоді для того аби ділянка покрита цими колами була зв’язана то має бути одне коло яке зєднане з двома іншими.
Тоді центр такого кола має бути на відстані не більше \(R\) до вершини, що воно покриває, бо інакше воно не буде покривати цю вершину. Також відстань до інших двох точок має бути не більше ніж \(3 \cdot R\), бо якщо більше, тоді ми не зможемо поставити коло яке буде покривати цю вершину і мати спільну точку на цьому колі. Тепер нам потрібно сказати чи може існувати такий центр кола. Для цього подивимось чи кола радіусів \(R\), \(3 \cdot R\) та \(3 \cdot R\), в заданих вершинах, мають спільну точку. Бо геометричним місцем точок, що не далі ніж на відстані \(d\) від даної точки — це коло в даній точці радіусу \(d\). Зауважте, що нам потрібно розглянути до якої точки з 3-х заданих відстань має бути менша рівна за \(R\), а до інших двох \(\le 3 \cdot R\).
У другому випадку ситуація буде подібною, але тут центр кола що містить дві точки має бути на відстані не більше \(R\) від цих двох точок. А відстань до третьої має бути не більша за \(5 \cdot R\), оскільки ми можемо розмістити коло, що не містить жодну точку, як коло для з’єднання.
Отже, нам необхідно знайти чи кола з радіусами \(R\), \(R\) та \(5 \cdot R\) мають спільну точку. Аналогічно до попереднього варіанту нам необхідно розглянути яка з 3-х точок буде мати коло радіуса \(5 \cdot R\).
У двох випадках нам потрібно сказати чи три кола мають хоча б одну спільну точку.
Таку підзадачу можна розв’язати так: розглянемо перетин двох кіл і подивимось чи належить цей перетин третьому колу, якщо так тоді у кіл є спільна точка. Зауважимо, що перетину може й не бути, тоді нічого не будемо перевіряти. Також необхідно розглянути перетин кожної пари кіл. Такий аглоритм буде працювати якщо у нас немає кола яке лежить в іншому. Проте є лише один варіант коли одне коло всередині іншого і існує спільна точка для 3-х кіл, але описаний вище алгоритм скаже протилежне.