Mock Bronze B3 · "Fence Painter"

← Back to mock contests · Original problem · Suggested time: 60–90 minutes

Problem

A fence of length L meters is painted with N strokes. The i-th stroke paints the segment [l_i, r_i] in color c_i. Later strokes overwrite earlier ones in the overlap region. After all strokes, find the total length of fence that is colored with exactly one specific color C.

Constraints

1 ≤ L ≤ 10⁶
1 ≤ N ≤ 1000
1 ≤ c_i, C ≤ 100
Time limit: 2 seconds, memory: 256 MB

Sample

Input
10 3 1
1 5 1
3 7 2
6 10 1

Output
3

Format: L N C on line 1, then N strokes. Output: meters painted color C at the end.

Skills this targets

Simulation across a 10⁶-meter fence — feasible in O(L) if you walk strokes carefully.
Choosing the right granularity: per-meter array vs. event sweep.
Off-by-one errors at segment endpoints (inclusive vs. exclusive).

Self-grade after attempting

Solution sketch (open after your timer is up)

Direct simulation. Allocate an array color[1..L]. For each stroke i from 1 to N, overwrite color[l..r] = c. Then count how many entries equal C. O(N·L) = 10⁹ worst case → too slow.
Better: reverse-sweep. Walk strokes from last to first; once a meter is "painted", skip it. Maintain a "next unpainted" pointer per index using a Union-Find-style jump array. O((L + N) α(L)).
Even simpler at this constraint. N ≤ 1000 means total stroke length is ≤ 10⁹, but each individual stroke is bounded by L=10⁶ and at most N=1000 strokes, so O(N · max_stroke_length) = 10⁹ worst-case. Reverse-sweep is the right call.
Watch the off-by-one: is r inclusive? Confirm from the statement.