wall砖墙

ID: 3955

远端评测题

1000ms

256MiB

尝试: 0

已通过: 0

难度: (无)

上传者:

小飞侠

题目描述

健佳正在用大小相同的砖块来砌起一面墙。这面墙由列砖块所组成，它们从左到右的编号0至n-1。各列的高度可

以不同。各列的高度就是该列砖块的数量。健佳用如下方式来建造这面墙。最开始每列都没有砖块。此后，健佳通

过k个阶段的增加(adding)或移除(removing)砖块操作来砌墙。当所有k个阶段完成后，这面墙就砌好了。在每个阶

段中，健佳都会被告知一个连续的砖块列的范围，以及一个高度值h，然后他就完成如下过程：在增加砖块(adding

)阶段，对于给定的列范围中高度小于h的列，健佳会增加砖块使它们的高度都恰好等于h。此时他不会改变那些高

度大于或等于h的列。在移除砖块(removing)阶段，对于给定的列范围中高度大于的列，健佳会移除砖块使它们的

高度都恰好等于h。此时他不会改变那些高度小于或等于h的列。你的任务就是计算出这面墙的最后形状。

输入格式

第1行：n, k。

第2+i 行(0≤i≤k-1)：op[i], left[i], right[i], height[i]。

n: 这面墙中的列数。

k: 阶段数。

op: 大小为k的数组；op[i]是第i个阶段的类型：1 表示增加阶段(adding) 而 2表示移除阶段(removing)

其中0≤i≤k-1。

left 和 right: 大小为k的数组；在第i个阶段中，列的范围从第left[i] 列开始到第right[i]列结束（包括两端

left[i] 和 right[i]），其中0≤i≤k-1。这里保证满足left[i]≤right[i]。

height: 大小为k的数组；height[i] 表示在阶段i的高度参数，其中0≤i≤k-1。

输出格式

共n行

第i行包含一个整数表示finalHeight[i]。

finalHeight: 大小为n的数组；你需要把第i列砖块的最终数量存放到finalHeight[i]中做为返回结果

其中0≤i≤n-1。

输入样例1
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
输入样例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

数据范围与约定

<w:WordDocument>

<w:View>Normal</w:View>

<w:Zoom>0</w:Zoom>

<w:PunctuationKerning />

<w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing>

<w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery>

<w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery>

<w:ValidateAgainstSchemas />

<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>

<w:IgnoreMixedContent>false</w:IgnoreMixedContent>

<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>

<w:Compatibility>

<w:SpaceForUL />

<w:BalanceSingleByteDoubleByteWidth />

<w:DoNotLeaveBackslashAlone />

<w:ULTrailSpace />

<w:DoNotExpandShiftReturn />

<w:AdjustLineHeightInTable />

<w:BreakWrappedTables />

<w:SnapToGridInCell />

<w:WrapTextWithPunct />

<w:UseAsianBreakRules />

<w:DontGrowAutofit />

<w:UseFELayout />

</w:Compatibility>

<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>

</w:WordDocument>

<![endif]--><!--[if gte mso 9]>

<w:LatentStyles DefLockedState="false" LatentStyleCount="156">

</w:LatentStyles>

<![endif]--><!--[if gte mso 10]>

/* Style Definitions */
table.MsoNormalTable
{mso-style-name:普通表格;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}

<![endif]--><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";

mso-hansi-font-family:"Times New Roman"">对于</span>100%<span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:

"Times New Roman"">的数据，</span>1<span style="font-size:

12.0pt;font-family:宋体;mso-bidi-font-family:Cambria">≤n≤2,000,000，1≤k≤500,000。</span>

2016.6.17时限放至60s

#P4364. wall砖墙

题目描述

输入格式

输出格式

数据范围与约定

还没有账户？

登录