10 条评论
-
zdw123 LV 7 @ 2015-10-18 13:12:11
确实太紧， nlogn 竟然要靠运气过。。。优化了下常数才没那么险...有四个点，我交了几次，最快1.5s,最慢2.5s...代码一样，为何会这样？
-
@ 2013-05-06 15:40:42
期考挂了来发题解...QAQ
一开始加入所有操作（操作序列顶指针＝ｍ）
之后原序列从左向右扫, 出现负数就将最后一个操作退掉（操作序列顶指针 - 1), 直到非负.
最后答案为操作序列顶指针编号 + 1.所有操作最多退一次, 所有元素均访问一次, O（n + m）
评测姬太给力了841ms(￣▽￣)~*...正确性什么的...应该好想所以懒说得了←_←
-
@ 2013-05-07 21:12:39
围观卖萌~>_<~
-
@ 2013-08-01 09:54:36
这个其实并不是O（n+m）= =
你仔细看一看：
无论是一开始插入所有操作，还是把最后一个操作退掉，你需要把该操作所覆盖的区域全部加上或减去dm。
这个至少需要O（logk）级的复杂度，而k的最坏情况是n，平均情况是n/2。
这个大小是不能忽略的。
所以总复杂度是O（n+（m）*logn）。
如果这样过了，那么就说明SegTree也能过= =
-
-
@ 2013-05-04 17:02:04
好像可以过了 不知道是数据弱了还是？
-
@ 2013-05-04 13:58:29
貌似PASCAL可以2181ms过的啊，二分法
话说有O(N+M)的吗？求大牛O(n+m)算法！ -
@ 2013-05-01 22:06:16
c++读入优化2100MS，pascal4036MS（pascal noip的时候T了的原代码）
-
@ 2013-05-01 21:59:12
轻松A掉，当初比赛写的pascal会T掉，源代码交上来A了，只能说明数据水了，或是评测机太优秀了
-
@ 2013-04-29 11:18:51
o(n+m)哪里有啊？
网上都是线段树、二分法～ -
@ 2013-04-28 09:56:13
发现野生球大牛一只，抱抱~
嗯其实有了O(n + m)就完全卡不掉了，啦啦啦~-
@ 2013-04-28 14:38:04
ORZ,当我没说
-
-
@ 2013-03-09 11:10:13
正在处理o. o。
-
@ 2013-03-08 21:36:31
再次惊现球大牛
- 1
