Skip to main content

Exactly K Roads

Challenge on lesson: Checkpoint — Difference Arrays

CHALLENGE
Difficulty: intermediate+25 XP

**Description:** A town has n intersections in a row. q new roads open, road i serving every intersection in [l_i, r_i]. Count the intersections served by **exactly k** roads. **Input:** Line 1: n q k (1 <= n, q <= 2*10^5, 0 <= k <= q). Next q lines: l r (1 <= l <= r <= n). **Output:** One integer — intersections with exactly k roads. **Example:** 5 2 1 / 1 2 / 2 4 -> 3 (intersections 1, 3, 4).

Back to lesson: Checkpoint — Difference Arrays