102473: [AtCoder]ABC247 D - Cylinder

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $400$ points

Problem Statement

We have a horizontal cylinder. Given $Q$ queries, process them in the given order.
Each query is of one of the following two types.

  • 1 x c: Insert $c$ balls, with a number $x$ written on each of them, to the right end of the cylinder.
  • 2 c: Take out the $c$ leftmost balls contained in the cylinder and print the sum of the numbers written on the balls that have been taken out.

We assume that the balls do never change their order in the cylinder.

Constraints

  • $1 \leq Q \leq 2\times 10^5$
  • $0 \leq x \leq 10^9$
  • $1 \leq c \leq 10^9$
  • Whenever a query of type 2 c is given, there are $c$ or more balls in the cylinder.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$Q$
${\rm query}_1$
$\vdots$
${\rm query}_Q$

The $i$-th query ${\rm query}_i$ is in one of the following two formats.

$1$ $x$ $c$
$2$ $c$

Output

Print the response to the queries of type 2 c in the given order, with newlines in between.


Sample Input 1

4
1 2 3
2 2
1 3 4
2 3

Sample Output 1

4
8
  • For the $1$-st query, insert $3$ balls, with a number $2$ written on each of them, to the right end of the cylinder.
    The cylinder has now balls with numbers $(2,2,2)$ written on them, from left to right.
  • For the $2$-nd query, take out the $2$ leftmost balls contained in the cylinder.
    The numbers written on the balls taken out are $2,2$, for a sum of $4$, which should be printed. The cylinder has now a ball with a number $(2)$ written on it, from left to right.
  • For the $3$-rd query, insert $4$ balls, with a number $3$ written on each of them, to the right end of the cylinder.
    The cylinder has now balls with numbers $(2,3,3,3,3)$ written on them, from left to right.
  • For the $4$-th query, take out the $3$ leftmost balls contained in the cylinder.
    The numbers written on the balls taken out are $2,3,3$, for a sum of $8$, which should be printed. The cylinder has now balls with numbers $(3,3)$ written on them, from left to right.

Sample Input 2

2
1 1000000000 1000000000
2 1000000000

Sample Output 2

1000000000000000000

Sample Input 3

5
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

Sample Output 3


There may be nothing you should print.

Input

题意翻译

您获得了一个队列,有 $Q$ 次操作,每次操作有以下两种可能: `1 x c`:代表将 $c$ 个数字 $x$ 弹进队列。 `2 c`:代表弹出队列前 $c$ 个数,并输出所有弹出的数的和。 你需要在每次第二种操作后输出正确的答案。保证在进行第二种操作时队列中至少有 $c$ 个数。 $1 \leq Q \leq 2 \times 10^5$,$0 \leq x \leq 10^9$,$1 \leq c \leq 10^9$。

Output

分数:400分 部分 问题描述 我们有一个水平放置的圆柱体。给定Q个查询,请按给定的顺序处理它们。 每个查询有两种类型之一。
  • 1 x c: 将带有数字x的c个球插入圆柱体的右端。
  • 2 c: 取出圆柱体中包含的最左边的c个球,并打印取出的球上数字之和。
我们假设球在圆柱体中永远不会改变顺序。 部分 约束
  • $1 \leq Q \leq 2\times 10^5$
  • $0 \leq x \leq 10^9$
  • $1 \leq c \leq 10^9$
  • 每当给出类型为2 c的查询时,圆柱体中都有c个或更多的球。
  • 输入中的所有值都是整数。
输入输出格式 输入 输入从标准输入以以下格式给出:
$Q$
${\rm query}_1$
$\vdots$
${\rm query}_Q$
第i个查询${\rm query}_i$有以下两种格式之一。
$1$ $x$ $c$
$2$ $c$
输出 按给定顺序打印对类型为2 c的查询的响应,中间用换行符分隔。 样例 样例输入1
4
1 2 3
2 2
1 3 4
2 3
样例输出1
4
8
  • 对于第1个查询,将带有数字2的3个球插入圆柱体的右端。
    现在圆柱体中从左到右有写有数字(2,2,2)的球。
  • 对于第2个查询,取出圆柱体中包含的最左边的2个球。
    取出的球上的数字为2,2,和为4,应该打印出来。 现在圆柱体中从左到右有写有数字(2)的球。
  • 对于第3个查询,将带有数字3的4个球插入圆柱体的右端。
    现在圆柱体中从左到右有写有数字(2,3,3,3,3)的球。
  • 对于第4个查询,取出圆柱体中包含的最左边的3个球。
    取出的球上的数字为2,3,3,和为8,应该打印出来。 现在圆柱体中从左到右有写有数字(3,3)的球。
样例输入2
2
1 1000000000 1000000000
2 1000000000
样例输出2
1000000000000000000
样例输入3
5
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
样例输出3

可能不需要打印任何内容。		  

加入题单

上一题 下一题 算法标签: