← 返回题目列表

AtCoder · s8pc_3_f

F. 寿司

中文机器翻译题面 查看原题
最高分数:$1200$ 积分

问题陈述

餐厅里有 $N$ 顾客。每个客户的编号为 $1$ 到 $N$。
一名寿司厨师为顾客进行了 $Q$ 的操作。

第 $i$ 个操作如下:
  1. 寿司厨师选择吃寿司菜数最少的顾客,即顾客$1,2,3,\dots,a_i$。如果有多个顾客的菜品数量最少,他就选择数量最少的顾客。
  2. 他把一盘寿司放在选定的座位上。
  3. 选择专业的顾客吃这个寿司。
  4. 重复 1-3 $b_i$ 次。

请计算每位顾客吃过的寿司的份数。

输入

输入由标准输入按以下格式给出:
$N \ Q$ $a_1\b_1$ $a_2\b_2$ $ : \ : $ $a_Q \ b_Q$

输出

  • 您必须打印 $N$ 行。
  • 第 $i$ 行应包含顾客 $i (1 \le i \le N)$ 吃过的寿司菜肴数量。

约束

  • $3 \le N, Q \le 100,000$
  • $1 \le a_i \le N$
  • $1 \le b_i \le 10^{12}$
  • 任何最终结果均不超过 $2 \times 10^{13}$。

子任务

子任务 1 [ $60$ 点 ]
  • $N,Q \le 100$
  • $b_i = 1$
子任务 2 [ $400$ 点 ]
  • $N,Q \le 100$
  • $b_i \le 10^{12}$
子任务 3 [ $240$ 点 ]
  • $N, Q \le 100,000$
  • $b_i = 1$
子任务 4 [ $500$ 点 ]
  • 没有其他限制。

示例输入 1

9 3
5 11
8 4
4 7

示例输出 1

4
4
4
4
2
2
1
1
0
吃过的寿司菜数变化如下:

客户 1 客户 2 客户 3 客户 4 客户 5 客户 6 客户 7 客户 8 客户 9
第一次操作 3 2 2 2 2 0 0 0 0
第二次操作 3 2 2 2 2 2 1 1 0
第三次操作 4 4 4 4 2 2 1 1 0

示例输入 2

6 6
3 5
6 11
1 6
4 7
5 2
2 5

示例输出 2

10
10
5
5
4
2

示例输入 3

5 6
1 1
2 1
3 1
1 1
5 1
3 1

示例输出 3

2
2
1
1
0

示例输入 4

10 10
10 10
9 20
8 30
7 40
6 50
5 60
4 70
3 80
2 90
1 100

示例输出 4

223
123
77
50
33
21
12
7
3
1
作者:E869120