この問題は主に一次元imos法を問います。
Easy の解説です。
配列を用いて質問毎に毎回答えるシミュレーションをしていくと、最悪 で時間制限に間に合いません。
そこで各質問を で事前に処理し、後々に累積和を用いたアルゴリズム( imos法 )を用いて実装してみます。この問題では各日にちにおいての予約数を要素とする配列 を定義し、これを用いて以下のように事前に処理し、累積和を用いることでそれぞれの日の予約数を合計 で求めることができます。
- 日目から 日目のそれぞれに予約が つずつ入る、すなわち区間 において に ずつ足していく時、 から足していくので とし、 からは予約が つ少なくなるため を格納する
また最後に予約数の最大値の導出とそのカウントですが、制約上最悪 が間に合うので愚直に探索し、愚直にカウントすればよいです。よって最初に入力する部分を含め この問題を解くことができます。
以下は解答例(C++)です。