236 . Wall

Submit out of contest
Status
Ranklist
Back to Problems List

TopCoder

暴力又被TLE
PY派對

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Algo Algo25_b

Description

頗汪是一個小小建築師，有一天他在幫 IOI2014 蓋一座牆。

這一坐牆總共有 $N$ 個牆面，這 $N$ 個牆面可以被視為一個很大的區間。

一開始每個牆面的高度都是 $0$，接下來頗汪會進行很多次操作。

頗汪的操作分成兩種：

  1. 將某個連續區間裡的牆面，高度不足 $h$ 的牆面補成高度 $h$。
  2. 將某個連續區間裡的牆面，高度超過 $h$ 的牆面變成高度 $h$。

在頗汪的所有操作結束之後，請你輸出整面牆的樣子。

Input Format

輸入的第一行有兩個正整數 $N$、$M$,中間用一個空白隔開。

接下來有 $M$ 行，每一行有四個非負整數 $op$、$L$、$R$、$h$，$op$ 代表操作種類，$L$、$R$代表這次操作的牆面是 $[L,R]$，$h$ 代表高度限制。

  • 對於第1筆測資：$1\leq{N,M}\leq10000,1\leq{h}\leq5000$
  • 對於第2筆測資：$1\leq{N,M}\leq10^ 5,1\leq{h}\leq5\times10^ 5$, 所有第1種操作都在第2種操作之前
  • 對於第3,4筆測資：$1\leq{N,M}\leq10^ 5,1\leq{h}\leq5\times10^ 5$
  • 對於第5~10筆測資：$1\leq{N,M}\leq2\times10^ 6,1\leq{h}\leq5\times10^ 5$

Output Format

對於每筆測試資料，請輸出 M 行，每行包含一個非負整數，依序代表每個牆面的最終高度.

Sample Input 1

10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412

Sample Output 1

0
0
0
39412
39412
39412
48623
48623
48623
48623

Sample Input 2

10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0

Sample Output 2

3
4
5
4
3
3
0
0
1
0

Hints

Problem Source

NEOJ Problem 259

IOI 2014

Subtasks

No. Testdata Range Constraints Score
1 0~5 10
2 6~11 10
3 12~20 10
4 21~29 10
5 30~34 10
6 35~39 10
7 40~44 10
8 45~49 10
9 50~54 10
10 55~59 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
1 1000 262144 65536 1
2 1000 262144 65536 1
3 1000 262144 65536 1
4 1000 262144 65536 1
5 1000 262144 65536 1
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 3
13 1000 262144 65536 3
14 1000 262144 65536 3
15 1000 262144 65536 3
16 1000 262144 65536 3
17 1000 262144 65536 3
18 1000 262144 65536 3
19 1000 262144 65536 3
20 1000 262144 65536 3
21 1000 262144 65536 4
22 1000 262144 65536 4
23 1000 262144 65536 4
24 1000 262144 65536 4
25 1000 262144 65536 4
26 1000 262144 65536 4
27 1000 262144 65536 4
28 1000 262144 65536 4
29 1000 262144 65536 4
30 1000 262144 65536 5
31 1000 262144 65536 5
32 1000 262144 65536 5
33 1000 262144 65536 5
34 1000 262144 65536 5
35 1000 262144 65536 6
36 1000 262144 65536 6
37 1000 262144 65536 6
38 1000 262144 65536 6
39 1000 262144 65536 6
40 1000 262144 65536 7
41 1000 262144 65536 7
42 1000 262144 65536 7
43 1000 262144 65536 7
44 1000 262144 65536 7
45 1000 262144 65536 8
46 1000 262144 65536 8
47 1000 262144 65536 8
48 1000 262144 65536 8
49 1000 262144 65536 8
50 1000 262144 65536 9
51 1000 262144 65536 9
52 1000 262144 65536 9
53 1000 262144 65536 9
54 1000 262144 65536 9
55 1000 262144 65536 10
56 1000 262144 65536 10
57 1000 262144 65536 10
58 1000 262144 65536 10
59 1000 262144 65536 10
Submit out of contest
Back to Top