#P17812. [ONTAK 2023]PIA

[ONTAK 2023]PIA

题目描述

在二维整数网格中模拟落沙,所有位置满足 y≥0y\ge0,每个位置至多容纳一粒沙子。初始没有沙子,y=0y=0 是沙子能够到达的最低一层,沙粒可以占据这一层。

当沙粒位于 (x,y)(x,y) 且 y>0y>0 时,按以下优先级移动:

  1. 若 (x,y−1)(x,y-1) 为空,向下移动;
  2. 否则,若 (x−1,y−1)(x-1,y-1) 为空,向左下移动;
  3. 否则,若 (x+1,y−1)(x+1,y-1) 为空,向右下移动;
  4. 否则停止。

到达 y=0y=0 后也停止移动。

需要依次处理 nn 次操作:

  • G x c:重复 cc 次,在 (x,1018)(x,10^{18}) 放下一粒沙子,等这粒沙子停止后再放下一粒;
  • Z x:询问横坐标为 xx 的这一列中有多少粒沙子。

输入格式

第一行一个整数 nn。接下来 nn 行,每行描述一次操作。

输出格式

对每次 Z 操作输出一行答案。查询的是粒数,而不是最上方沙粒的纵坐标。

数据范围

2≤n≤1000002\le n\le100000,∣x∣≤5×108|x|\le5\times10^8,每次投放满足 1≤c≤10121\le c\le10^{12}。

样例

7
G 0 11
Z 0
G 5 3
Z 3
G 4 1
G -1 1
Z 3
3
0
1