Can anyone explain me solution with interval tree? or any other solution?
P.S. I understand Russian
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3843 |
2 | jiangly | 3705 |
3 | Benq | 3628 |
4 | orzdevinwang | 3571 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | jqdai0815 | 3530 |
8 | ecnerwala | 3499 |
9 | gyh20 | 3447 |
10 | Rebelz | 3409 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 171 |
2 | adamant | 163 |
2 | awoo | 163 |
4 | TheScrasse | 157 |
5 | nor | 153 |
6 | maroonrk | 152 |
6 | -is-this-fft- | 152 |
8 | Petr | 145 |
9 | orz | 144 |
9 | pajenegod | 144 |
Название |
---|
есть n точек в 3d x[i], y[i], z[i]
для простоты предположим что все координаты различны (по x , по y и по z)
сортируем по убыванию параметра x[i], затем по убыванию y[i]. делаем сжатие координат.
пусть a[i] = -inf для всех 1 <= i <= K (K = 10^6 например, после того как пожали координаты)
и на данном массиве мы умеем искать максимум на любом интервале (L, R) за O(log(n)) , и обновлять значение в ячейке за O(log(n)).
рассматриваем точки в том порядке в котором посортировали
ищем максимум на интервале (y[i], K) если он больше чем z[i], то соответствующая дама потенциальная самоубийца.
обновляем a[y[i]] = max(a[y[i]], z[i]);
Ссуть в песок. А массив нужен для определения того есть ли дама со всеми тремя параметрами больше чем у i-той, меньшесть координаты x обеспечивается тем, что дамы обрабатываеются в порядке убывания её, по координате y это обеспечивается с помошью индекса в массиве, мы находим максимальную координату z которая уже была(т.е по X все ОК) в куске массива где y[j] > y[i], и сравниваем это с нашим z.массив А реализуется деревом отрезков.