Overview

Given multiple rainy days (intervals) during which work cannot be done, the problem asks us to count only the days when seeds can be planted and find the last day needed to finish planting \(N\) seeds.

Analysis

Key Observations

• Takahashi can only plant seeds on “non-rainy days,” and he can plant at most 1 seed per day.
• Therefore, we count “plantable days” in chronological order, and the day when the total reaches \(N\) is the answer.
• However, since the number of days and the endpoints of rainy intervals can be up to \(10^{18}\), simulating one day at a time is far too slow (TLE).

Why the Naive Approach Fails

• For example, even if rain continues until around day \(10^{18}\), naively incrementing from day = 1 would require \(10^{18}\) loop iterations, which is impossible.

Solution Strategy

• Since rainy days are given as “intervals,” we process them as whole intervals.
• In particular, if rainy intervals overlap or are adjacent, merging them into a single interval simplifies the processing.
  • Example: \([2,5]\) and \([4,7]\) overlap, so they merge into \([2,7]\)
  • Example: \([2,5]\) and \([6,8]\) are adjacent (\(5+1=6\)), and since there are no plantable days in between, they can be merged into \([2,8]\)

After merging, we only need to count the “number of consecutive sunny days (gaps) before each rainy interval,” allowing us to skip ahead through dates efficiently.

Algorithm

1. Read all rainy intervals \([L_i, R_i]\) and sort them in ascending order of \(L_i\).
2. Iterate through the sorted intervals and merge overlapping or adjacent ones (\(l \leq cur\_r + 1\)) to create a list of non-overlapping intervals merged.
3. Start with day = 1 (current day) and planted = 0 (number planted), then process merged from left to right.
   • For the current rainy interval \([l, r]\):
     • If day < l, then days from day to \(l-1\) are sunny, so gap = l - day seeds can be planted.

          - If `planted + gap >= N`, planting finishes within this sunny interval.
       

       • The remaining number needed is \(N - planted\), so the answer is
         \(day + (N - planted) - 1\)

            - Otherwise, update `planted += gap` and `day = l`.
         

     • Next, since we enter the rainy interval, skip day to the day after the rain ends: r + 1 (when day <= r).
4. After processing all rainy intervals, the remaining remaining = N - planted seeds can be planted on consecutive sunny days, so the answer is
   \(day + remaining - 1\)

Concrete Example

• \(N=5\), rainy intervals are \([2,3]\), \([5,5]\):
  • Sunny: day 1 (1 seed)
  • Days 2–3 are rainy (skip)
  • Day 4 is sunny (2nd seed)
  • Day 5 is rainy (skip)
  • Days 6, 7, 8… plant the remaining 3 seeds → completed on day 8
    As we can see, we only need to count the “consecutive sunny portions.”

Complexity

• Time complexity: \(O(M \log M)\) (dominated by sorting; merging and scanning are \(O(M)\))
• Space complexity: \(O(M)\) (for storing the interval array and merge results)

Implementation Notes

• Rainy intervals are inclusive on both endpoints, so work can resume from day r+1.

• The merge condition must include not only “overlap” but also “adjacency,” using l <= cur_r + 1 (since there are no sunny days in between).

• Endpoints can be up to \(10^{18}\), so in Python there is no integer overflow concern, but the implementation should always account for this range.

• When \(M=0\), there is no rain, so the answer is simply day \(N\).

  Source Code

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)

    if M == 0:
        print(N)
        return

    intervals = [(next(it), next(it)) for _ in range(M)]
    intervals.sort()

    merged = []
    cur_l, cur_r = intervals[0]
    for l, r in intervals[1:]:
        if l <= cur_r + 1:
            if r > cur_r:
                cur_r = r
        else:
            merged.append((cur_l, cur_r))
            cur_l, cur_r = l, r
    merged.append((cur_l, cur_r))

    day = 1
    planted = 0

    for l, r in merged:
        if day < l:
            gap = l - day
            if planted + gap >= N:
                ans = day + (N - planted) - 1
                print(ans)
                return
            planted += gap
            day = l
        if day <= r:
            day = r + 1

    remaining = N - planted
    ans = day + remaining - 1
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.