[COCI 2012/2013 #2] INSPEKTOR

Luogu

IDLGP8300

Time4000ms

Memory32MB

DifficultyP6

2012COCI（克罗地亚）

一个新城镇刚刚在一个小国家落成。像往常一样，Mirko 获得了首席税务监察员的职位。他的职责是确保镇上所有不同公司的充分会计处理。沿大街有 $N$ 个营业厅，从左到右编号为 $1\sim N$。一开始所有的办公室都是空的；随着时间的推移，公司将进出这些办公室。不时，Mirko 会经过一些办公室，只检查这些办公室中目前最富有的一家。搬入的公司用四个整数来描述： - $T$：搬入的日期。此处设小镇建成当天为 $1$。 - $K$：办公室序号。 - $Z$：公司的每日利润（如果公司亏损，则可能为负数）。 - $S$：搬入当天公司账户余额。如果办公室 $K$ 中已经有一家公司，则当新公司搬入时，该公司搬出。新公司直到搬入后的第二天才开始营业（或赚取利润）。米尔科的巡视由三个整数描述： - $T$：巡视的日期。小镇建成当天为 $1$。 - $A,B$：Mirko 将会经过 $[A,B]$ 内所有办公室。由于 Mirko 只在一天结束时工作，所以到 Mirko 散步时，所有公司都已经完成了当天的业务并公布了当天的利润。帮助 Mirko 编写一个程序，在每次闲逛时查找 Mirko 路过的当前最富有的公司的账户余额。 ## Input 输入的第一行包含两个正整数，$N\ (1 ≤ N ≤ 10^5)$ 和 $M \ (1 ≤ M ≤ 3\times 10^5)$，分别表示办公室和巡视的数量。接下来 $M$ 行，每一行包含一个事件的描述，格式为 `1 T K Z S`（公司搬入）或 `2 T A B`（Mirko 的巡视）。所有事件都按时间顺序给出，每天最多发生一个事件（即 $T$ 将是严格递增）。最后一个事件的天数将小于 $10^6$, 所有 $Z$ 和 $S$ 数字的绝对值值将小于 $10^6$。 ## Output 对于 Mirko 的每一次巡视，输出一行包含 Mirko 检查的公司的账户余额，或者如果他将经过的所有办公室都是空的，则输出单词 `nema`。 [samples] ## Background **本题分值按 COCI 原题设置，满分 $160$。**

Samples

Input #1

Output #1

12
17

Input #2

3 6
1 1 1 4 -2
1 2 2 2 6
2 3 3 1
2 4 3 1
1 5 3 -6 20
2 6 2 3

Output #2

8
10
14

Input #3

Output #3

-1
nema
7
31
17

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2012/2013 #2] INSPEKTOR",
    "description": {
      "content": "一个新城镇刚刚在一个小国家落成。 像往常一样，Mirko 获得了首席税务监察员的职位。 他的职责是确保镇上所有不同公司的充分会计处理。 沿大街有 $N$ 个营业厅，从左到右编号为 $1\\sim N$。一开始所有的办公室都是空的； 随着时间的推移，公司将进出这些办公室。 不时，Mirko 会经过一些办公室，只检查这些办公室中目前最富有的一家。 搬入的公司用四个整数来描述： - $T$：搬入的日",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 32768
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8300"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一个新城镇刚刚在一个小国家落成。 像往常一样，Mirko 获得了首席税务监察员的职位。 他的职责是确保镇上所有不同公司的充分会计处理。\n\n沿大街有 $N$ 个营业厅，从左到右编号为 $1\\sim N$。一开始所有的办公室都是空的； 随着时间的推移，公司将进出这些办公室。 不时，Mirko 会经过一些办公室，只检查这些办公室中目前最富有的一家。\n\n搬入的公司用四个整数来描述：\n\n- $T$：搬入的日...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments