Integer Points in Rational Intervals
National Olympiad — National round
Submission name: segments.cpp
Problem summary
Given intervals with rational endpoints and independently open or closed ends, count distinct integer points belonging to their union. Reversed or degenerate intervals may be empty.
Input
n; then n records: opening bracket, a b c d, closing bracket, all separated by spaces. The endpoints are a/b and c/d.
Output
Number of covered integer points.
Constraints
0<n<200000; −10^17<a,c<10^17; 0<b,d<10^17.
Worked example
An independently prepared example for this explanation.
Input
3 ( -3 2 5 2 ] [ 2 1 4 1 ) [ 8 1 8 1 ]
Output
6
Solution analysis
- Convert each rational interval to an inclusive integer interval. Closed left uses ceil(a/b), open left uses floor(a/b)+1; closed right uses floor(c/d), open right uses ceil(c/d)−1.
- Discard empty integer intervals and sort the rest.
- Merge overlapping or adjacent integer ranges and sum end−start+1.
Why it works
The rounding formulas select exactly the integers satisfying the endpoint inequalities, including negative fractions. Merging preserves the union and removes duplicate counting.
Watch out. C++ division truncates toward zero, so explicitly implement mathematical floor for negative numerators. No floating-point arithmetic is needed.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The rounding formulas select exactly the integers satisfying the endpoint inequalities,
// including negative fractions. Merging preserves the union and removes duplicate counting.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
using namespace std;
long long flo(long long a,long long b){
long long q=a/b;
if(a%b<0){
--q;
}
return q;
}
long long cei(long long a,long long b){
return -flo(-a,b);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<pair<long long,long long>>v;
while(n--){
char x,y;
long long a,b,c,d;
cin>>x>>a>>b>>c>>d>>y;
long long l=x=='['?cei(a,b):flo(a,b)+1,r=y==']'?flo(c,d):cei(c,d)-1;
if(l<=r){
v.push_back({l,r});
}
}
sort(v.begin(),v.end());
long long ans=0,l=0,r=-1;
bool have=false;
for(auto[a,b]:v){
if(!have){
l=a;
r=b;
have=true;
}
else if(a<=r+1){
r=max(r,b);
}
else{
ans+=r-l+1;
l=a;
r=b;
}
}
if(have){
ans+=r-l+1;
}
cout<<ans<<'\n';
}