問題一覧 > 通常問題

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

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

問題文

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

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

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

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

入力

$N\ M$
$L_1\ R_1$
$\vdots$
$L_M R_M$

  • $1\leq N\leq 5\times 10^5$
  • $1\leq M\leq 5\times 10^5$
  • $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

$1$人目は $4$ 日前～ $1$ 日前、$2$人目は $3$ 日前～ $2$ 日前、$3$人目は $4$ 日前だけ参加しているので、
$5$ 日前から $1$ 日前までの参加者は、それぞれ $0,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もしくは右上の雲マークをクリックしてアカウントを作成してください。