問題一覧 > 通常問題

No.674 n連勤

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 121
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm / テスター : ei1333333ei1333333
2 ProblemId : 1601 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-04-09 13:42:43

問題文

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

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