| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 11 | 4 | 4 | 66.667% |
На проектной смене в образовательном центре <<Сириус>> участники одной из команд проектируют промышленных роботов.
Роботы будут наполнять деталями $n$ контейнеров, которые стоят в ряд и пронумерованы от 1ドル$ до $n$. В $i$-й контейнер можно суммарно поместить не больше $a_i$ деталей. Участники собрали $m$ роботов. Изначально у $j$-го робота имеется $c_j$ деталей, часть из которых он положит в контейнеры. Также, у $j$-го робота есть диапазон действия, задающийся двумя числами $l_j \le r_j,ドル означающий, что робот может класть детали только в контейнеры с номерами от $l_j$ до $r_j$ включительно. Роботы пытаются суммарно положить в контейнеры как можно больше деталей.
Созданные роботы бывают двух типов. Если тип робота $t_j = 0,ドル то его диапазон действия всегда остается неизменным. А роботов типа $t_j = 1$ можно перепрограммировать. Если контейнер с номером $x$ выделить как наиболее важный, диапазон действия каждого робота типа 1ドル$ расширяется минимальным образом, чтобы он стал содержать контейнер $x$. Более формально, диапазон действия робота номер $j,ドル имеющего тип 1ドル,ドル изменяется на $[\min(l_j, x), \max(r_j, x)]$.
Для каждого $x$ от 1ドル$ до $n$ вычислите, какое максимальное количество деталей роботы смогут суммарно поместить в контейнеры, если важным будет контейнер с номером $x,ドル а роботы будут действовать оптимальным образом.
Каждый тест состоит из нескольких наборов входных данных. В первой строке дано одно целое число $t$ (1ドル \leq t \leq 200,000円$) --- количество наборов входных данных. Далее следуют описания наборов входных данных.
В первой строке каждого набора входных данных даны два целых числа $n$ и $m$ (1ドル \le n, m \le 200,000円$) --- количество контейнеров и роботов соответственно.
В следующей строке даны $n$ целых чисел $a_i$ (0ドル \le a_i \le 10^9$) --- вместимости контейнеров.
В каждой из следующих $m$ строк даны по четыре целых числа $l_j,ドル $r_j,ドル $c_j,ドル $t_j$ (1ドル \le l_j \le r_j \le n,ドル 0ドル \le c_j \le 10^9,ドル $t_j \in \{0, 1\}$) --- диапазон действия, изначальное количество деталей и тип робота соответственно.
Обозначим за $\sum n$ сумму $n,ドル а за $\sum m$ сумму $m$ по всем наборам входных данных в одном тесте. Гарантируется, что $\sum n \leq 200,000円,ドル $\sum m \leq 200,000円$.
Для каждого набора входных данных выведите $n$ целых чисел --- ответ на задачу для всех $x$ от 1ドル$ до $n$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $\sum n \leq 100,ドル $\sum m \leq 100,ドル $m = 1$ |
| 2 | 7 | $\sum n \leq 100,ドル $\sum m \leq 100$ |
| 3 | 6 | $\sum n \leq 2000,ドル $\sum m \leq 2000$ |
| 4 | 6 | $\sum n \leq 20,000円,ドル $\sum m \leq 200$ |
| 5 | 12 | $\sum n \leq 10^5,ドル $\sum m \leq 2000$ |
| 6 | 17 | $\sum n \leq 20,000円,ドル $\sum m \leq 20,000円,ドル $t_i = 1$ |
| 7 | 8 | $\sum n \leq 10^5,ドル $\sum m \leq 10^5,ドル $l_i \le l_{i + 1},ドル $r_i \le r_{i + 1},ドル $t_i = 1$ |
| 8 | 8 | $\sum n \leq 10^5,ドル $\sum m \leq 10^5,ドル $t_i = 1$ |
| 9 | 13 | $\sum n \leq 10^5,ドル $\sum m \leq 10^5,ドル для всех роботов с $t_i = 0,ドル $r_i \le 50$ или $l_i > n - 50$ |
| 10 | 4 | $\sum n \leq 10^5,ドル $\sum m \leq 10^5,ドル $a_i = 1$ |
| 11 | 6 | $\sum n \leq 10^5,ドル $\sum m \leq 10^5$ |
| 12 | 3 | $\sum n \leq 2 \cdot 10^5,ドル $\sum m \leq 2 \cdot 10^5$ |
1 4 3 3 3 2 2 1 2 2 0 3 3 3 0 2 2 4 1
8 7 7 8