bzoj#P3463. [COCI2012] Inspector

[COCI2012] Inspector

题目描述

在一个小国家中,一个新的小镇终于建成了!如往常一样,Mirko 获得了首席税务巡查员的职位。他的任务是保证正确地计算各公司的收入情况。一共有 NN 家办公室坐落在主干道上,从左到右被编号为 1N1-N。一开始,所有办公室一开始都是空的。随后,一些公司会搬入或搬出某些办公室。Mirko 时不时地会经过某些办公室并审查在这些办公室中,最富有的公司的账目。

一个公司被以如下的方式描述:

  • TT: 表示搬入的第一天。

  • KK: 表示搬入的办公室的标号。

  • ZZ: 公司每日的盈利。(可以是负值表示亏损)

  • SS: 公司搬入时的公司财务情况。(即公司的账户资金,也可以是负值)

如果一家公司已经在 KK 办公室了,当有新公司要进入 KK 办公室时,这家公司会立刻搬出。

新公司第一天并不会运营,盈利从第二天开始计算。

Mirko 的审查以 33 个整数来描述:

  • TT: 审查的时间。

  • AABB: Mirko 会检查 AA 办公室至 BB 办公室(包括 AABB)之间的公司。

Mirko 只会在一天结束时检查,所有公司这时已经计算完成了当天利润。

输入格式

第一行包含 2 个正整数:N(1N100000)N(1\leq N\leq 100000) 表示办公室的数量和 M(1M300000)M(1\leq M\leq 300000) 表示事件的个数。

接下来 MM 行,遵循以下格式:1 T K Z S2 T A B(含义如题目描述)。其中 TT 会严格递增,并且最后一天小于 10000001000000, 且 Z,S<1000000|Z|, |S| < 1000000。 (注意 AA 可能大于BB

输出格式

对于每次 Mirko 的审查,每行输出一个整数,表示当天最富有的公司的资产(可以为负)。

如果 Mirko 经过的所有办公室中都没有公司入驻,则输出 nema\text{nema}

5 9
1 1 5 4 -5
2 2 3 5
1 3 4 6 9
2 4 1 2
1 6 2 2 3
2 8 2 1
1 9 4 0 17
2 10 5 5
2 11 1 4
-1
nema
7
31
17

题目来源

By Jason Hsiao