These are the notes for Competitive Programming episode 9. Episodes 7 and 8 gave every position its own array cell. Here positions go up to 10^9, so that rule breaks: an array would need about 3.7 GB, and walking every position gets Time Limit Exceeded. The fix keeps only the order of the few numbers that appear (like runners lined up by bib number): sort, unique + erase, lower_bound. That is coordinate compression. Then we run episode 7's difference array on the compressed points, with real piece lengths, and see two bugs with their real outputs. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The problem: Festival Road
Problem I · Festival Road (written for this course). A road has positions
1 .. 10^9. There arenlamp strings; stringilights every integer position fromltor(both included). Print two numbers: the largest number of strings on one position, and how many positions are lit by at least one string.
1 ≤ n ≤ 2·10^5,1 ≤ l ≤ r ≤ 10^9.
| Sample input | Sample output |
|---|---|
43 75 121000000 10000036 6 |
3 14 |
Position 6 is under three strings ([3,7], [5,12], [6,6]). The lit positions are 3..12 (10 positions) and 1000000..1000003 (4 positions): 14.
Why the old tricks fail
An array per position. Episode 7's difference array needs a cell for every position. How big is that?
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll cells = 1000000001; // positions 0 .. 10^9
ll bytes = cells * sizeof(int);
cout << bytes / (1024 * 1024) << " MB\n";
return 0;
}
Output:
3814 MB
Almost 4 GB against a typical 256 MB limit: Memory Limit Exceeded.
A map, walking every position. A map (a sorted key → value table that only stores keys you insert) avoids the giant array:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
map<int, int> lamps;
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
for (int x = l; x <= r; x++) lamps[x]++;
}
int best = 0;
for (auto [x, c] : lamps) best = max(best, c);
cout << best << ' ' << lamps.size() << '\n';
return 0;
}
It prints 3 14 on the sample. On three long strings (1 1000000000, 2 999999999, 500000000 500000000) it walks about 2·10^9 positions and gets Time Limit Exceeded in the SyntaxPilot compiler. The cost grows with the length of the road, not with n.
The observation. There are only 2n endpoints (at most 4·10^5 numbers), and between two neighbouring endpoints nothing changes. Only those numbers, and their order, matter.
The idea: bib numbers on sports day
| On sports day | In code |
|---|---|
| Bibs 7, 42, 100, 1000000000: huge numbers, few runners | values up to 10^9, only a few of them |
| Line the runners up by bib number | sort |
| The same bib twice is the same runner | unique + erase |
| Each runner gets a lane 0, 1, 2, 3 by his place in the line | lower_bound gives each value its index |
Coordinate compression
Coordinate compression replaces each value by its index among the sorted distinct values. The order is kept: a < b exactly when id(a) < id(b).
vector<int> xs = a; // copy the values
sort(xs.begin(), xs.end()); // 1. sort
xs.erase(unique(xs.begin(), xs.end()), xs.end()); // 2. drop repeats
int id = lower_bound(xs.begin(), xs.end(), v) - xs.begin(); // 3. index of v
uniquemoves consecutive repeats to the end and returns an iterator to where the clean part stops; it does not shrink the vector.erasecuts off the rest.lower_boundis a built-in binary search: it returns an iterator (a pointer-like position) to the first element that is not less thanv. Subtractingxs.begin()turns it into an index.- Cost: sorting
O(n log n), each lookupO(log n).
The six values from the video:
| a | 100 | 7 | 1000000000 | 7 | 42 | 100 |
| sorted | 7 | 7 | 42 | 100 | 100 | 1000000000 |
| unique xs | 7 | 42 | 100 | 1000000000 | ||
| index | 2 | 0 | 3 | 0 | 1 | 2 |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
vector<int> xs = a;
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
for (int i = 0; i < n; i++) {
int id = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
cout << id << " \n"[i == n - 1];
}
return 0;
}
Input 6 / 100 7 1000000000 7 42 100, output:
2 0 3 0 1 2
The missing-unique bug (real output)
Delete the xs.erase(unique(...), xs.end()); line and run the same input:
3 0 5 0 2 3
The order is still right, but indices skip: the largest is 5 with only 4 distinct values. Any array sized by the number of distinct values now goes out of bounds, and equal values that should be next to each other get gaps between them.
Back to the road: compress l and r + 1
A string switches on at l and off at r + 1. Those are the only places the answer can change, so compress all l and r + 1 values (at most 2n points) and run the difference array on the points: +1 at id(l), −1 at id(r + 1). Between point k and point k + 1, the lamps don't change, and that piece of road is xs[k+1] − xs[k] positions long.
The sample:
| k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| xs[k] | 3 | 5 | 6 | 7 | 8 | 13 | 1000000 | 1000004 |
| lamps on piece k | 1 | 2 | 3 | 2 | 1 | 0 | 1 | |
| piece length | 2 | 1 | 1 | 1 | 5 | 999987 | 4 |
Maximum 3; lit = 2 + 1 + 1 + 1 + 5 + 4 = 14.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> l(n), r(n), xs;
for (int i = 0; i < n; i++) {
cin >> l[i] >> r[i];
xs.push_back(l[i]);
xs.push_back(r[i] + 1);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
auto id = [&](int v) { return lower_bound(xs.begin(), xs.end(), v) - xs.begin(); };
vector<int> d(xs.size() + 1, 0);
for (int i = 0; i < n; i++) {
d[id(l[i])]++;
d[id(r[i] + 1)]--;
}
int cur = 0, best = 0;
ll lit = 0;
for (int k = 0; k + 1 < (int)xs.size(); k++) {
cur += d[k];
best = max(best, cur);
if (cur > 0) lit += xs[k + 1] - xs[k];
}
cout << best << ' ' << lit << '\n';
return 0;
}
| Input | Output |
|---|---|
| the sample | 3 14 |
3 / 1 1000000000 / 2 999999999 / 500000000 500000000 |
3 1000000000 (instantly) |
The r vs r + 1 bug (real output)
Compressing r instead of r + 1 (and subtracting at id(r) + 1) prints, on the sample:
3 1000000
The maximum is still right, but the length is wrong. The string [5, 12] should switch off at 13, but 13 was never recorded as a point; the next recorded point after 12 is 1000000, so the light "stays on" across the whole dark gap. Rule: every position where the answer changes must be a point. A stress test against the map brute force on small positions (episode 5) catches this immediately.
Solutions in C++, Java and Python
C++: the Festival Road program above.
Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken(); int n = (int) st.nval;
int[] l = new int[n], r = new int[n];
int[] xs = new int[2 * n];
for (int i = 0; i < n; i++) {
st.nextToken(); l[i] = (int) st.nval;
st.nextToken(); r[i] = (int) st.nval;
xs[2 * i] = l[i];
xs[2 * i + 1] = r[i] + 1;
}
Arrays.sort(xs);
int m = 0;
for (int i = 0; i < xs.length; i++) if (i == 0 || xs[i] != xs[i - 1]) xs[m++] = xs[i];
int[] d = new int[m + 1];
for (int i = 0; i < n; i++) {
d[Arrays.binarySearch(xs, 0, m, l[i])]++;
d[Arrays.binarySearch(xs, 0, m, r[i] + 1)]--;
}
int cur = 0, best = 0;
long lit = 0;
for (int k = 0; k + 1 < m; k++) {
cur += d[k];
best = Math.max(best, cur);
if (cur > 0) lit += xs[k + 1] - xs[k];
}
System.out.println(best + " " + lit);
}
}
Python
import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
l = list(map(int, data[1:2 * n + 1:2]))
r = list(map(int, data[2:2 * n + 2:2]))
xs = sorted(set(l + [x + 1 for x in r]))
d = [0] * (len(xs) + 1)
for a, b in zip(l, r):
d[bisect_left(xs, a)] += 1
d[bisect_left(xs, b + 1)] -= 1
cur = best = lit = 0
for k in range(len(xs) - 1):
cur += d[k]
best = max(best, cur)
if cur > 0:
lit += xs[k + 1] - xs[k]
print(best, lit)
main()
All three print 3 14 on the sample (Python and Java tested with the same input).
Brute force vs optimal
| Map per position | Array of 10^9 | Compressed | |
|---|---|---|---|
| Time | O(total length · log) up to 2·10^14 | O(10^9) | O(n log n) |
| Memory | grows with the length | 3.7 GB | O(n) |
| Verdict at the limits | TLE | MLE | instant |
Common mistakes (and the real messages)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
sort without unique + erase |
3 0 5 0 2 3 instead of 2 0 3 0 1 2 |
repeats keep their own slots | xs.erase(unique(xs.begin(), xs.end()), xs.end()) |
Compressing r instead of r + 1 |
3 1000000 instead of 3 14 |
the switch-off point is missing | push l and r + 1 |
unique without erase |
junk values left at the end of xs |
unique doesn't change the size |
erase from its return value |
lit as int |
overflow on long roads | lengths add up past 2.1·10^9 in harder versions | long long |
vector<int> d(1000000001) |
Memory Limit Exceeded | 3814 MB | compress first |
| Looking up a value that was never inserted | wrong index (lower_bound returns the next bigger one) |
r was compressed, then r + 1 was looked up |
look up only values you pushed |
Mini project: dense ranks
Give every student's score a rank starting from 1, where equal scores share a rank and there are no gaps (a dense rank). It is compression plus one:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
vector<int> xs = a;
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
for (int i = 0; i < n; i++)
cout << lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin() + 1 << " \n"[i == n - 1];
}
Input 4 / 90 75 90 60, output: 3 2 3 1.
Practice
-
Change Festival Road to print how many positions are covered by at least 2 strings.
Answer
Replace <code>if (cur > 0)</code> with <code>if (cur >= 2)</code>. On the sample it prints <code>3 3</code> (positions 5, 6, 7). -
Why do we compress
r + 1and notr?Answer
The lamps change right after <code>r</code>, at <code>r + 1</code>. Every position where the count changes must be a point, or a piece will wrongly extend to the next recorded point. -
What does the rank program print for
5 / 3 3 3 3 3?Answer
<code>0 0 0 0 0</code>: one distinct value. -
Count pairs
i < jwitha[i] > a[j](inversions) when values go up to 10^9.Answer
Compress the values to 0..m−1 so they fit an array, then count with merge sort or a counting structure in O(n log n). Compression is the step that makes the array small enough. -
Values are
long longup to 10^18. What changes?Answer
Only the types: <code>vector<long long> xs</code>. Sorting and <code>lower_bound</code> work the same.
Quick quiz
Input 4 / 50 20 50 90. What does the rank program print?
A) 1 0 1 2 · B) 2 0 2 3 · C) 1 0 2 3 · D) 0 1 0 2
Answer
A. xs = [20, 50, 90], so 50 → 1, 20 → 0, 50 → 1, 90 → 2. Without unique it prints 1 0 1 3 (real output).
Interview questions
- What is coordinate compression and when do you need it? Mapping values to their rank among the sorted distinct values. Needed when values are huge (10^9) but few (2·10^5), and you want arrays indexed by value.
- Why
erase(unique(...))and not justunique?uniqueonly moves repeats to the end and returns the new logical end;eraseremoves them. - How do you get a value's compressed index?
lower_bound(xs.begin(), xs.end(), v) - xs.begin(), O(log n). - Union length of many intervals with coordinates up to 10^9? Compress the endpoints (
landr + 1for closed integer intervals), sweep with a running count, and addxs[k+1] − xs[k]for pieces with count > 0. - Does compression change the answer of an order-based question? No: it keeps the order, so comparisons, sorting and "how many smaller" questions are unchanged.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Coordinate | A position or value on a line | position 1000000 on the road |
| Coordinate compression | Replacing each value by its index among the sorted distinct values | 100 → 2 in [7, 42, 100, 10^9] |
| Rank | A value's place in sorted order | 7 has rank 0 |
| Dense rank | Rank where ties share a number and there are no gaps | 90 75 90 60 → 3 2 3 1 |
map |
A sorted key → value table that stores only inserted keys | lamps[x]++ |
sort |
Puts a range in increasing order, O(n log n) | 7 7 42 100 100 10^9 |
unique |
Moves consecutive repeats to the end, returns the new end | used inside erase |
erase |
Removes a range of elements from a vector | cuts off the repeats |
| Iterator | A pointer-like position inside a container | xs.begin() |
lower_bound |
Binary search: first element not less than v | index of 100 is 2 |
| Binary search | Halving a sorted range to find a value in O(log n) | lower_bound |
| Event point | A position where the answer can change | l and r + 1 |
| Piece | The stretch between two neighbouring points | 8..12, length 5 |
| Memory Limit Exceeded (MLE) | The program used more memory than allowed | 3814 MB array |
| Lambda | A small unnamed function written inline | auto id = [&](int v) { ... } |
Summary
- Values up to 10^9 but only
2·10^5of them: keep only their order. sort,erase(unique(...)),lower_bound − begin: O(n log n), indices 0..m−1, order kept.- Forgetting
uniquemakes indices skip (3 0 5 0 2 3). - For segments: compress
landr + 1, run the difference array on the points, add piece lengthsxs[k+1] − xs[k]. - Compressing
rinstead ofr + 1printed3 1000000instead of3 14.
Next episode: two pointers on contest problems: sliding windows in O(n).