Can anyone explain me solution with interval tree? or any other solution?
P.S. I understand Russian
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 165 |
3 | adamant | 161 |
4 | TheScrasse | 160 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | orz | 146 |
9 | SecondThread | 145 |
9 | pajenegod | 145 |
Название |
---|
есть 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.массив А реализуется деревом отрезков.