| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 15 | 4 | 3 | 75.000% |
Компьютерная система управления станциями на Меркурии состоит из $n$ серверов, пронумерованных от 1ドル$ до $n$. Серверы соединены $(n - 1)$ двусторонними каналами связи, $i$-й из которых соединяет $i$-й и $(i+1)$-й серверы.
С Земли необходимо передать пакет обновления программного обеспечения для компьютерной системы управления. Пакет необходимо установить на каждый сервер. Стоимость передачи пакета обновления с Земли на Меркурий очень высока, поэтому с Земли пакет обновления передаётся только на один сервер. Затем пакет необходимо передать на все остальные серверы по каналам связи, возможно, через другие серверы.
Из-за высокой солнечной радиации на Меркурии передавать пакет обновления по каналам связи можно только в некоторые промежутки времени. Для $i$-го канала связи известен промежуток времени $[l_i, r_i],ドル во время которого возможна передача пакета по этому каналу. Пакет передаётся по любому каналу связи мгновенно.
Пакет обновления, переданный на $j$-й сервер, немедленно устанавливается и помещается в специальный буфер памяти, из которого он может быть передан на другие серверы. Пакет находится в буфере памяти $j$-го сервера в течение $t_j$ секунд с момента его получения. Если в момент нахождения пакета в буфере памяти сервера появляется возможность передать его по каналу связи на соседний сервер, на котором пакет обновления пока не установлен, то он немедленно передаётся по этому каналу связи.
Поскольку пакет содержит важные обновления, требуется начать его распространение как можно раньше.
Требуется написать программу, которая для всех $i$ от 1ドル$ до $n$ определяет, возможно ли установить пакет обновления на все серверы, передав его с Земли на $i$-й сервер. Если это возможно, то необходимо определить, в какой минимальный неотрицательный момент времени можно установить пакет на этот сервер, чтобы в результате обновление оказалось установлено на всех серверах.
Первая строка входных данных содержит $n$ --- количество серверов (1ドル \le n \le 200,000円$).
Вторая строка содержит $n$ целых чисел $t_1, t_2, \ldots, t_n,ドル где $t_j$ --- время нахождения пакета в буфере памяти $j$-го сервера (0ドル \le t_j \le 10^9$).
Следующие $(n-1)$ строк описывают каналы связи. Для описания $i$-го канала задаются два целых числа $l_i$ и $r_i$ --- границы промежутка времени, на протяжении которого возможна передача пакета по этому каналу (0ドル \le l_i \le r_i \le 10^9$).
Выходные данные должны содержать $n$ целых чисел $a_1, a_2, \ldots, a_n$.
Число $a_i$ должно быть равно такому минимальному неотрицательному моменту времени, что при установке пакета обновления на $i$-й сервер в момент $a_i,ドル пакет будет в итоге установлен на всех серверах. Если такого момента времени для $i$-го сервера не существует, необходимо вывести $a_i = -1$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | 1ドル \leq n \leq 500,ドル 0ドル \leq t_i \leq 500,ドル 0ドル \leq r_i \leq 500$ |
| 2 | 10 | 1ドル \leq n \leq 5000,ドル $t_i = 5000,ドル 0ドル \leq r_i \leq 5000$ |
| 3 | 10 | 1ドル \leq n \leq 5000,ドル 0ドル \leq t_i \leq 5000,ドル $r_i = 5000$ |
| 4 | 10 | 1ドル \leq n \leq 5000,ドル 0ドル \leq t_i \leq 5000,ドル 0ドル \leq r_i \leq 5000$ |
| 5 | 15 | 1ドル \leq n \leq 200,000円,ドル $t_i = 10^9,ドル 0ドル \leq r_i \leq 10^9$ |
| 6 | 15 | 1ドル \leq n \leq 200,000円,ドル 0ドル \leq t_i \leq 10^9,ドル $r_i = 10^9$ |
| 7 | 20 | 1ドル \leq n \leq 200,000円,ドル 0ドル \leq t_i \leq 10^9,ドル 0ドル \leq r_i \leq 10^9$ |
1 10
0
2 3 5 6 8
3 1
3 1 2 4 7 10 3 5
-1 5 5
4 1 0 3 2 4 6 5 5 7 10
5 5 4 -1
В первом примере имеется всего один сервер, минимальное подходящее время, в которое можно установить на него обновление --- 0.
Во втором примере есть два сервера, передать обновление между которыми можно в промежуток от 6 до 8. Первый сервер хранит обновление в буфере 3 единицы времени, а второй --- 5 единиц времени. Если отправить обновление первому серверу в момент 3, то он передаст его второму серверу в момент 6. Аналогично если отправить обновление второму серверу в момент 1, то он передаст его первому серверу в момент 6.
В третьем примере нельзя передать обновление первому серверу так, чтобы оно передалось третьему серверу, так как канал 2--3 закрывается до того, как открывается канал 1--2. Можно отправить обновление второму или третьему серверу в момент 5. В этот момент канал 2--3 открыт, поэтому его сразу получат второй и третий серверы. В момент 7, когда откроется канал 1--2 обновление ещё будет находиться в буфере второго сервера, и передастся первому серверу.
В четвёртом примере второй сервер хранит пакет 0 единиц времени, а канал 2--3 открыт в промежуток 5--5. Чтобы передать обновление через второй сервер к третьему серверу, оно должно попасть ко второму серверу в момент 5. Если же мы хотим отправить обновление третьему серверу, то это можно сделать в момент 4, при этом оно будет храниться до момента 7 и будет в итоге установлено на все серверы.