logo AlgoBeat OnlineJudge
登录 注册

#103179. [BZOJ 3179] [Coci2012]RASPORED

内存限制:128 MiB 时间限制:20000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有n个订单,第i个订单需要你花费Ti的时间完成。若第i个订单在时刻t完成则 你的收益等于Li-t。总收益是各个订单收益的和。你可以自由地安排订单的完成顺 序。订单会发生m次变化。每j次变化是将第Vj个订单的内容更新为Lj’和Tj’。现 在要求你快速计算出最初的和每次变化后你的最大收益。

样例

样例输入

4 2 
3 2 
0 3 
4 3 
4 1 
3 0 4 
1 4 5 

样例输出

-8 
-13 
-18

数据范围与提示

n, m <= 200,000. Ti, Li <= 10,0000.