Міський горизонт

Міський горизонт. Задача 7747 (https://www.e-olymp.com/uk/problems/7747)

Фермер Джон приїхав зі своїми коровами в місто! Під час заходу сонця корови дивляться на міський горизонт і спостерігають красиві силуети, утворені прямокутними будинками.

Весь горизонт представлений числовою прямою з n (1 ≤ n ≤ 40000) будівлями. Силует i-го будинку розпростерся уздовж горизонту між точками a_i і b_i (1 ≤ a_i <b_i ≤ 10⁹) та має висоту h_i (1 ≤ h_i ≤ 10⁹). Визначте площу у квадратних одиницях загального силуету, утвореного усіма n будівлями.

Вхідні дані: Перший рядок містить ціле число n. Кожна з наступних n рядків описує будівлю i трьома цілими числами: a_i, b_i і h_i.

Вихідні дані: Виведіть загальну площу міського силуету у квадратних одиницях, утвореного усіма n будівлями.

Ідея розв'язку

• 1. Зчитуємо кількість будівель n.

  2. Зчитуємо даны про будівелі у двовимірний масив розмірами n на 3.

  3. Сортуємо увесь масив по а_і.

  4. Знаходимо найвищу будівлю, найбільше значеня h_i. Назвемо його h_max. Його індекс i_max.

  5. Розпочнемо обчислення площі S з обчислення площі найвищої будівлі (b_imax - a_imax)_*h_max.

  6. Далі ідемо від i_max у двох напрямках. Наприклад спочатку до меших і. Потім те ж саме зробимо у сторону збільшення індексів.

  7. Якщо b наступної будівлі більше від а попередньої то будівлі перекриваються і замість цього b ми беремо а попередньої. ...