Count Covering Segments
National Olympiad — Municipal round (2015 season)
Submission name: points.cpp
Problem summary
For each query coordinate, count the closed segments containing it. Endpoints may arrive in either order.
Input
N M, then N endpoint pairs and M query coordinates.
Output
M coverage counts in query order.
Constraints
1 ≤ N,M ≤ 100000; coordinates in [−10^9,10^9]; equal endpoints allowed.
Worked example
An independently prepared example for this explanation.
Input
3 4 2 5 7 3 5 10 4 11 5 8
Output
2 0 3 1
Solution analysis
- Normalize each segment so its left endpoint is at most its right endpoint. Sort the left endpoints and right endpoints separately.
- At x, count all segments that have started, meaning left ≤ x, and subtract those already finished, meaning right < x. Two binary searches compute these counts.
- At x=5 in the example, three segments have started and none has ended strictly before 5, so the answer is 3. At x=11 all three have ended, giving zero.
Why it works
Every containing segment contributes one to the started count and zero to the finished count. Segments wholly left contribute one to each and cancel; those wholly right contribute neither. Hence their difference is precisely the coverage.
Watch out. The right-endpoint test is strict: a segment includes both endpoints. Keep query order.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
// Algorithm: Normalize each segment so its left endpoint is at most its right endpoint.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<int>left(n),right(n);
for(int i=0;i<n;++i){
cin>>left[i]>>right[i];
if(left[i]>right[i]){
swap(left[i],right[i]);
}
}
sort(left.begin(),left.end());
sort(right.begin(),right.end());
for(int i=0;i<m;++i){
int x;
cin>>x;
auto started=upper_bound(left.begin(),left.end(),x)-left.begin();
auto finished=lower_bound(right.begin(),right.end(),x)-right.begin();
if(i>0){
cout<<' ';
}
cout<<started-finished;
}
cout<<'\n';
}