You have parking spots numbered 1 to N. Each light is hung above one spot P and shines from P – S to P + S, clipped to stay inside 1..N. Then you get Q questions, each asking whether a particular parking spot is lit by at least one light. Since N, L, and Q can each be as large as 500,000, checking every light for every question would be too slow.

Key Concepts

• Interval coverage
• Difference array
• Prefix sums
• Preprocessing for O(1) queries

Thinking Process

Each light covers one continuous interval. For a light at position P with spread S, compute left = max(1, P – S) and right = min(N, P + S). Instead of marking every covered spot, mark only the boundary changes: add 1 at left and subtract 1 just after right. A prefix sum then tells us how many lights cover each parking spot. If the coverage at a queried spot is greater than 0, print Y; otherwise, print N.

Solution #1: Brute Force

The most direct idea is to mark every parking spot that each light covers. This is simple and useful for understanding the problem, but it can be too slow when N, L, and Q are large.

# CCC 2026 J5/S2 - Beams of Light
# Solution #1: Brute Force, Mark every lit spot directly

# Read input
N = int(input())   # number of parking spots
L = int(input())   # number of lights
Q = int(input())   # number of questions

# lit[i] will tell us whether parking spot i is illuminated
# We use size N + 1 so we can use indices 1 to N directly
lit = [False] * (N + 1)

# Process each light
for _ in range(L):
    P, S = map(int, input().split())

    # Find the interval this light covers
    left = max(1, P - S)
    right = min(N, P + S)

    # Mark every spot in this interval as illuminated
    for i in range(left, right + 1):
        lit[i] = True

# Answer each question
for _ in range(Q):
    x = int(input())

    if lit[x]:
        print('Y')
    else:
        print('N')

Solution #2: Difference Array

The optimized solution marks only the start and end boundary changes for each light. After one prefix sum pass, every query can be answered in O(1).

Python Solution

import sys
input = sys.stdin.readline

N = int(input())
L = int(input())
Q = int(input())

diff = [0] * (N + 2)

for _ in range(L):
    P, S = map(int, input().split())
    left = max(1, P - S)
    right = min(N, P + S)
    diff[left] += 1
    diff[right + 1] -= 1

covered = [False] * (N + 1)
current = 0
for i in range(1, N + 1):
    current += diff[i]
    covered[i] = current > 0

answers = []
for _ in range(Q):
    x = int(input())
    answers.append('Y' if covered[x] else 'N')

print('\n'.join(answers))

C++ Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, L, Q;
    cin >> N >> L >> Q;

    vector<int> diff(N + 2, 0);

    for (int i = 0; i < L; i++) {
        int P, S;
        cin >> P >> S;
        int left = max(1, P - S);
        int right = min(N, P + S);
        diff[left]++;
        diff[right + 1]--;
    }

    vector<bool> covered(N + 1, false);
    int current = 0;
    for (int i = 1; i <= N; i++) {
        current += diff[i];
        covered[i] = current > 0;
    }

    while (Q--) {
        int x;
        cin >> x;
        cout << (covered[x] ? 'Y' : 'N') << '\n';
    }

    return 0;
}

Complexity Analysis

Building the difference array takes O(L). Computing the prefix sums takes O(N). Answering all queries takes O(Q). The total time complexity is O(N + L + Q), and the memory usage is O(N).

Common Mistakes

• Marking every spot covered by every light, which can be too slow for large spreads.
• Forgetting to clip intervals to the valid range 1..N.
• Forgetting the -1 update at right + 1.
• Using nested loops over lights and queries.

Learning Outcomes

• Recognize interval coverage problems.
• Use a difference array to apply many range updates efficiently.
• Use prefix sums to convert boundary changes into actual coverage.
• Preprocess once so each query can be answered in O(1).