这道题时限卡得太紧了吧

借教室
球威 LV 8 @ 12 年前

RT
pascal全军覆没啊....
admin改一下时限吧...

zdw123 LV 7 @ 9 年前

确实太紧， nlogn 竟然要靠运气过。。。优化了下常数才没那么险...有四个点，我交了几次，最快1.5s,最慢2.5s...代码一样，为何会这样？
sumi LV 7 @ 12 年前

期考挂了来发题解...QAQ

一开始加入所有操作（操作序列顶指针＝ｍ）
之后原序列从左向右扫, 出现负数就将最后一个操作退掉（操作序列顶指针 - 1), 直到非负.
最后答案为操作序列顶指针编号 + 1.

所有操作最多退一次, 所有元素均访问一次, O（n + m）
评测姬太给力了841ms(￣▽￣)~*...

正确性什么的...应该好想所以懒说得了←_←
- vistaswx LV 5 MOD @ 12 年前
  
  围观卖萌~>_<~
- htwc LV 8 @ 11 年前
  
  这个其实并不是O（n+m）= =
  你仔细看一看：
  无论是一开始插入所有操作，还是把最后一个操作退掉，你需要把该操作所覆盖的区域全部加上或减去dm。
  这个至少需要O（logk）级的复杂度，而k的最坏情况是n，平均情况是n/2。
  这个大小是不能忽略的。
  所以总复杂度是O（n+（m）*logn）。
  如果这样过了，那么就说明SegTree也能过= =
Dumpling_李 LV 9 @ 12 年前

好像可以过了不知道是数据弱了还是？
绿色的云 LV 10 @ 12 年前

貌似PASCAL可以2181ms过的啊，二分法
话说有O(N+M)的吗？求大牛O(n+m)算法！
Lugh LV 7 @ 12 年前

c++读入优化2100MS，pascal4036MS（pascal noip的时候T了的原代码）
Lugh LV 7 @ 12 年前

轻松A掉，当初比赛写的pascal会T掉，源代码交上来A了，只能说明数据水了，或是评测机太优秀了
vcvycy LV 8 @ 12 年前

o(n+m)哪里有啊？
网上都是线段树、二分法～
sumi LV 7 @ 12 年前

发现野生球大牛一只，抱抱~
嗯其实有了O(n + m)就完全卡不掉了，啦啦啦~
- 球威 LV 8 @ 12 年前
  
  ORZ,当我没说
mrw LV 10 MOD @ 12 年前

正在处理o. o。
Totoro LV 8 @ 12 年前

再次惊现球大牛