[NERC 2018] King Kog’s Reception

Luogu

IDLGP9801

Time2600ms

Memory512MB

DifficultyP6

2018ICPCNERC/NEERC

有些骑士想要拜访国王，但是由于这里的骑士都很遵守礼节，他们都会提前预约好他要来拜访的时刻和拜访将持续的时间。骑士按照接待处记录的时刻顺序依次拜访国王，每个骑士必须等前面的骑士结束拜访。很不幸，公主也准备要来拜访国王，但善良的公主并不会为此而打乱骑士们拜访的顺序，而她会等待骑士们拜访完了再来拜访，请你计算公主要等多长时间。 ## Input 共 $q+1$ 行。第一行一个整数 $q (1 \leq q \leq 3 \times 10^5)$。然后 $q$ 行，先是一个字符。 - 如果字符是 `+`，紧跟在后面两个数字，表示骑士 $i$ 要于 $t (1 \leq t \leq 10^6)$ 时刻到达，拜访时间 $d(1 \leq d \leq 10^6)$ 时间单位。 - 如果字符是 `-`，后面一个数字 $i(1 \leq i \leq q)$，表示骑士 $i$ 暂时取消了他的预约。 - 如果字符是 `?`，后面一个数字 $t (1 \leq t \leq 10^6)$，表示公主将于 $t$ 时刻拜访。 ## Output 对于每个 `?`，输出一行，表示公主要等待多长时间。注意此处公主拜访时骑士的预约记录只有前面的几个，并不包含后面加进来的。 [samples] ## Background 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) K 题。 ## Note 对于所有数据，保证 $1 \leq q \leq 3 \times 10^5$，$1 \leq t \leq 10^6$，$1 \leq d \leq 10^6$。

Samples

Input #1

19
? 3
+ 2 2
? 3
? 4
+ 5 2
? 5
? 6
+ 1 2
? 2
? 3
? 4
? 5
? 6
? 7
? 9
- 8
? 2
? 3
? 6

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[NERC 2018] King Kog’s Reception",
    "description": {
      "content": "有些骑士想要拜访国王，但是由于这里的骑士都很遵守礼节，他们都会提前预约好他要来拜访的时刻和拜访将持续的时间。骑士按照接待处记录的时刻顺序依次拜访国王，每个骑士必须等前面的骑士结束拜访。 很不幸，公主也准备要来拜访国王，但善良的公主并不会为此而打乱骑士们拜访的顺序，而她会等待骑士们拜访完了再来拜访，请你计算公主要等多长时间。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2600,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9801"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有些骑士想要拜访国王，但是由于这里的骑士都很遵守礼节，他们都会提前预约好他要来拜访的时刻和拜访将持续的时间。骑士按照接待处记录的时刻顺序依次拜访国王，每个骑士必须等前面的骑士结束拜访。\n\n很不幸，公主也准备要来拜访国王，但善良的公主并不会为此而打乱骑士们拜访的顺序，而她会等待骑士们拜访完了再来拜访，请你计算公主要等多长时间。\n\n## Input\n\n共 $q+1$ 行。\n\n第一行一个整数 $q (1...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments