Overview

This problem asks: when planting \(N\) seeds in total, one per day on days when it is not raining (sunny days), on what day will the last seed be planted?

Analysis

1. Limitations of Simulation

The number of seeds to plant \(N\) can be up to \(10^9\), and the endpoints of rain periods \(R_i\) can be up to \(10^{18}\), which are extremely large values. Therefore, a simulation that “advances one day at a time and plants a seed if it’s sunny” will not run within the time limit (TLE).

2. Organizing Rain Periods

Up to \(M\) rain periods (at most \(10^5\)) are given, but they may overlap with each other. For example, if it rains from day 3 to day 5 and from day 4 to day 7, these can be merged into a single interval “day 3 to day 7.”

3. Thinking in Blocks of Sunny Days

Between the organized rain periods, there are consecutive blocks of “sunny days.” 1. Set the current date to day \(1\). 2. Calculate the number of sunny days until the next rain period begins. 3. If all \(N\) seeds can be planted within that number of days, the answer is determined within that block. 4. If not, subtract that number of days from \(N\) and advance the date to the day after the rain period ends.

By jumping the date in “period (block)” units rather than one day at a time, we can solve this efficiently.

Algorithm

1. Merging Rain Periods:
   • Sort the given \(M\) rain periods \([L_i, R_i]\) in ascending order of start day \(L_i\).
   • If the end of the previous interval overlaps with (or is consecutive to) the start of the next interval, merge them into a single interval.
2. Scanning Sunny Periods:
   • Set current_day (the next candidate day for planting a seed) to \(1\).
   • Iterate through the merged rain periods in order.
   • Calculate the number of sunny days: sunny_len = (rain start day \(L\)) - current_day.
   • If \(N \le \text{sunny\_len}\), the answer is current_day + N - 1.
   • Otherwise, reduce \(N\) by sunny_len and update current_day to (rain end day \(R\)) + \(1\).
3. Handling the Remainder:
   • If seeds still remain after passing through all rain periods, plant them all at the end. The answer is current_day + N - 1.

Complexity

• Time Complexity: \(O(M \log M)\)
  • Sorting the rain periods takes \(O(M \log M)\).
  • Merging and scanning the intervals can be done in \(O(M)\).
• Space Complexity: \(O(M)\)
  • \(O(M)\) memory is used to store the input intervals and the merged intervals.

Implementation Notes

• Interval Merging: After performing intervals.sort(), comparing the current endpoint curr_r with the next start point next_l and merging if next_l <= curr_r is a classic technique for problems involving intervals.

• Handling Large Numbers: Since values can be as large as \(10^{18}\), you need to use a language that supports arbitrary-precision integers like Python, or use the long long type in C++.

• No Rain Case: Implement carefully to handle corner cases such as when \(M=0\) or when all seeds are planted before any rain period begins.

  Source Code

import sys

# 問題文の要件に従い、N個の種を植え終える最後の日を求めます。
# 毎日1個ずつ種を植えますが、雨の期間[L_i, R_i]には作業ができません。
# 作業ができる日（晴れの日）を1日目から数えて、N番目の晴れの日を特定します。

def solve():
    # 全ての入力を一度に読み込み、効率的に処理するためにイテレータを使用します。
    # Nは非常に大きい(最大10^9)ため、シミュレーションではなく計算で求めます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # 雨の期間がない場合、N番目の種は第N日に植えられます。
    if M == 0:
        print(N)
        return
        
    # 雨の期間を取得します。
    intervals = []
    for _ in range(M):
        try:
            l = int(next(it))
            r = int(next(it))
            intervals.append((l, r))
        except StopIteration:
            break
            
    # 雨の期間を結合するために、開始日でソートします。
    intervals.sort()
    
    # 重なり合っている、あるいは連続している雨の期間を1つの区間に結合します。
    merged = []
    it_intervals = iter(intervals)
    try:
        curr_l, curr_r = next(it_intervals)
    except StopIteration:
        print(N)
        return

    for next_l, next_r in it_intervals:
        # 現在の区間の終わりと次の区間の始まりが重なっていれば結合します。
        if next_l <= curr_r:
            if next_r > curr_r:
                curr_r = next_r
        else:
            # 重なりがなければ、現在の区間を確定させて次の区間に移ります。
            merged.append((curr_l, curr_r))
            curr_l, curr_r = next_l, next_r
    # 最後の区間を追加します。
    merged.append((curr_l, curr_r))
    
    # current_day は次に種を植える候補となる日（最初は1日目）です。
    current_day = 1
    for l, r in merged:
        # 現在の日から次の雨が始まる前日までの「晴れの日」の数を計算します。
        # 晴れの期間は [current_day, l - 1] です。
        sunny_len = l - current_day
        if sunny_len > 0:
            if N <= sunny_len:
                # 残りの種 N 個をすべてこの晴れの期間中に植えられる場合、
                # その日は current_day から数えて N 日目になります。
                print(current_day + N - 1)
                return
            else:
                # この期間だけでは足りない場合、植えられるだけ植えて N を更新します。
                N -= sunny_len
        
        # 次に種を植えられる可能性があるのは、この雨の期間が終わった翌日です。
        current_day = r + 1
    
    # すべての雨の期間が終わった後、残りの種を順番に植えていきます。
    # N個目の種は current_day から N-1 日経過した日に植えられます。
    print(current_day + N - 1)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.