No.674 n連勤

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 39
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm / テスター : ei1333ei1333

1 ProblemId : 1601 / 出題時の順位表

問題文

A君は$0$日から${D-1}$日までの$D$日間の間で仕事の予定が入ります。
$D$日間の前後に仕事は無く最初は$D$日間の間にも仕事の予定はありません。

これから仕事の予定が$Q$個入ります。
$i$番目の仕事の予定は$D$日間の間で$A_i$日目から$B_i$日目までという形で入ります。
仕事の予定が1つ以上入っている日はかならず出勤することになります。
仕事が1つも無い日は出勤しません。

例えば、0日目から3日目まで仕事の予定が入っていて4日目に仕事が無いと4連勤となります。
仕事が入るたびに$D$日間の間に最大何連勤が存在するかを答えよ。

入力

$D$ $Q$
$A_0$ $B_0$
$A_1$ $B_1$
$\vdots$
$A_{Q-1}$ $B_{Q-1}$

$D$は期間の日数。$D$は整数。$1 \le D \le 1000000000000000000 = 10^{18}$。
$Q$は仕事の予定の数。$Q$は整数。$1 \le Q \le 30000 = 3 \times 10^4$。
$A_i$、$B_i$はi番目の指示での日目。$A_i$、$B_i$は整数。$0 \le A_i \le B_i \le {D-1}$。

出力

仕事の予定が入るたびに$D$日間の間に最大何連勤が存在するかを答えよ。
答えのすべての行で改行すること。

サンプル

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

0日から1日に仕事の予定が入ると0日から1日までの2連勤が最大です。
6日から8日に仕事の予定が入ると6日から8日までの3連勤が最大です。
2日から7日に仕事の予定が入ると0日から8日までの9連勤が最大です。

サンプル2
入力
10 4
3 7
3 5
1 1
4 9
出力
5
5
5
7

サンプル3
入力
1000000000000000000 2
0 999999999999999999
0 999999999999999999
出力
1000000000000000000
1000000000000000000

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。