你们竟然还Hack.......%%%%%%%%%

hhd

已加，但我并不是作者

回复 @zys :
ORZ

回复 @Satoshi :
有两种做法：
一种是2008rank1做法的改进版
另一种是我的做法，在状态之间连转移边，构建拓扑图
都是n^3的，不过不知道为什么我的这么慢。。。。。。

回复 @stone :
所以Rank1的做法是什么......

回复 @Satoshi :
M是任意两点之间边数。

回复 @Satoshi :
但是那些写DP的估计写挂了的过不了。所以时限放宽到1s。加这题是为了宣传Rank1的做法。

回复 @stone :
M是什么，你们写的是DP吗？

回复 @Satoshi :
O(NM)，本来时限是0.5s的

回复 @溪哥 :
你们是怎么写的?貌似看着是O(n^2)

回复 @Satoshi :

作者请加数据范围

同样是n^3的做法，为什么差别这么大？

证明：
Sort the haybales by location. Consider two haybales i and j such that Bessie can start somewhere between those haybales and break through all the haybales from i+1 to j−1, but she can't break haybale i or haybale j.
It must be the case then that no haybale between i and j is strictly taller than those two.
That motivates the following O(NlogN)solution:
Sort the haybales in decreasing order of size. Consider having an empty road, and place the haybales in that order. When placing a haybale, look immediately to its left and to its right and see if you can break through either one of those haybales if you were inside that interval. Mark that interval as "trapped" if so.
This will be O(NlogN)
as long as you check to make sure that the interval isn't already marked as trapped.
按重量从大到小排序，可以保证区间不会被漏掉

莫比乌斯反演的裸题。。

我竟然把sv设成0了。。。都可以去卖萌了QAQ

这个题竟然半颗星....

最后一句话亮了...话说让他切题的那个人做我右面的右面的左面

最后一句话亮了...话说让他切题的那个人做我右面的右面