Hi all. Could some please make me understand what it is with an example? I'll appreciate it. DO you have some problems to apply it?
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 163 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 13.05.2026 06:15:01 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
In Chinese: 离散化(ie. map larger values to smaller distinct values)
please explain cordinate compression someone i can't solve a problem relating to this please help me
Let's say that in a problem, you're required to store N (1 <= N <= 10^5) elements and perform some operations on those elements (say put them in a Segment Tree). Normally, if the elements were also in the range (1, 10^5), inserting them into a data structure would be a cinch.
Say, for example, the elements are now in the range (1, 10^12). Now simply inserting elements into a Segment Tree is not possible because you cannot allocate memory for 10^12 integers. This is where coordinate compression comes into play.
Let's read in all of the possible numbers, sort them, and assign each of them a number based off of increasing order. Because N is <= 10^5, the maximum number you assign is going to be 10^5. Thus, by compressing the "coordinates", we maintain the relative order of points in a memory-efficient manner.
I hope this helps!
Hey, thanks for the nice explanation. I have a doubt,
If we have numbers ranging 0,10^9 and i want to update and access their frequency in O(1). Unordered_map,map gave me TLE. Can there be a better than O(lgn) way, using coordinates compression to solve this problem ?
Thanks !
Use unordered_map after choosing random modulo(hash function) to prevent anti-hash tests to make solutions to fail. See this.
Though I got an alternate solution from some blog, but thanks a lot !
You're welcome!
where , is the other blog?
Good problem http://usaco.org/index.php?cpid=207&page=viewproblem2
It's when you take some coordinates, put them all in a hydraulic press. Then they become "compressed".
You're a funny guy
Check this video out.