問題一覧 > 通常問題

No.2154 あさかつの参加人数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 197
作問者 : Michirakara / テスター : kotamanegi KowerKoint2010 hibit_at mo124121
2 ProblemId : 8384 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-09 19:19:01

問題文

hibit 君は毎朝バーチャルコンテスト「あさかつ」を開催していますが、 NN 日前までのあさかつの順位表をなくしてしまいました。

しかし、彼は誰がいつ参加していたかは覚えています。

また、参加者は全部で MM 人おり、ii 人目は LiL_i 日前から RiR_i 日前のあさかつだけ に参加し、それ以外の日には参加していないもの とします。

NN 日前から昨日まで、それぞれ何人があさかつに参加していたかを改行区切りで出力してください。

入力

N MN\ M
L1 R1L_1\ R_1
⋮\vdots
LMRML_M R_M

  • 1≤N≤5×1051\leq N\leq 5\times 10^5
  • 1≤M≤5×1051\leq M\leq 5\times 10^5
  • 1≤Ri≤Li≤N(1≤i≤M)1\leq R_i\leq L_i\leq N (1\leq i\leq M)
  • 入力はすべて整数

サンプル

サンプル1
入力
5 3
4 1
3 2
4 4
出力
0
2
2
2
1

11人目は 44 日前～ 11 日前、22人目は 33 日前～ 22 日前、33人目は 44 日前だけ参加しているので、
55 日前から 11 日前までの参加者は、それぞれ 0,2,2,2,10,2,2,2,1 となります。

サンプル2
入力
1 1
1 1
出力
1

悲しいことに、あさかつに参加していたのは hibit 君だけだったようです。

サンプル3
入力
9 8
2 1
7 3
8 2
6 4
5 5
8 3
3 2
8 8
出力
0
3
3
4
5
4
4
3
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。