Camera Coverage of City Zones
National Olympiad — National round (2025 season)
Submission name: cameras.cpp
Problem summary
N zones form a line. Each of Q cameras is installed at a listed zone and watches that zone and up to R zones on either side, clipped at the city boundaries. Several cameras may share a zone. Find how many cameras watch each zone.
Input
N; then Q R; then Q camera positions.
Output
N coverage counts in zone order.
Constraints
1 ≤ N,Q ≤ 100000; 0 ≤ R < N; 1 ≤ camera position ≤ N.
Worked example
An independently prepared example for this explanation.
Input
10 4 2 5 4 1 4
Output
1 3 4 3 3 3 1 0 0 0
Solution analysis
- Each camera adds one over an interval [max(1,c−R),min(N,c+R)]. Updating every covered cell separately could require NQ work.
- Use a difference array: add one at the interval’s left endpoint and subtract one immediately after the right endpoint. A prefix sum reconstructs how many camera intervals are currently active.
- In the sample, the two cameras at zone 4 both cover zones 2…6 and must both be counted. After combining their updates with cameras at 5 and 1, the prefix sums are 1,3,4,3,3,3,1,0,0,0.
Why it works
For each camera, the prefix sum includes its +1 from the first covered zone until the −1 just after its last zone. Thus it contributes exactly one inside its coverage interval and zero outside. Summing these independent contributions gives the correct count at every zone.
Watch out. Clip both interval endpoints. Allocate an extra position for right+1, and retain duplicate cameras rather than deduplicating positions.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q, radius;
cin >> n >> q >> radius;
vector<int> difference(n + 2, 0);
for (int i = 0; i < q; i++) {
int position;
cin >> position;
int left = max(1, position - radius);
int right = min(n, position + radius);
// Activate at left and deactivate immediately after the inclusive right end.
difference[left]++;
difference[right + 1]--;
}
int active = 0;
for (int zone = 1; zone <= n; zone++) {
active += difference[zone];
if (zone > 1) {
cout << ' ';
}
cout << active;
}
cout << '\n';
}