Coloring
National Olympiad — Municipal round (2009 season)
Submission name: color.cpp
Problem summary
Integer points 1 through 500000 start white. Toggle every point of each inclusive interval. Find the longest final run of consecutive black points.
Input
N, followed by N pairs a b.
Output
The longest black run length, or zero if there are no black points.
Constraints
1 ≤ N ≤ 5000; 1 ≤ a ≤ b ≤ 500000.
Worked example
Official statement example.
Input
2 3 7 5 10
Output
3
Solution analysis
- An interval toggle changes parity at its left endpoint and immediately after its right endpoint. Record these changes with XOR in a difference array.
- Scan coordinates from 1 through 500000, maintaining the XOR prefix. A parity of one means black: extend the current run; otherwise reset it. Track its maximum.
- For [3,7] and [5,10], overlap points 5 through 7 are toggled twice and return to white. The black runs are [3,4] and [8,10], with lengths 2 and 3.
Why it works
At coordinate x the XOR prefix contains one contribution for exactly those intervals covering x, so it equals the final color. The scan measures every maximal black run and therefore reports the longest.
Complexity: O(N+500000) time and O(500000) space.
Watch out. Toggle at b+1, not at b.,Repeated intervals cancel.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: At coordinate x the XOR prefix contains one contribution for exactly those intervals
// covering x, so it equals the final color. The scan measures every maximal black run and therefore
// reports the longest.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
vector<unsigned char>delta(500002,0);
while(n--){
int a,b;
cin>>a>>b;
delta[a]^=1;
delta[b+1]^=1;
}
int parity=0,run=0,answer=0;
for(int x=1;x<=500000;++x){
parity^=delta[x];
run=parity?run+1:0;
answer=max(answer,run);
}
cout<<answer<<'\n';
}