27181번 - Большие вызовы 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 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
1 4 3 3 3 2 2 1 2 2 0 3 3 3 0 2 2 4 1
예제 출력 1
8 7 7 8
채점 및 기타 정보
- 예제는 채점하지 않는다.