Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1 2 3
  1  Болтрушевич Егор Юрьевич, 11 октября 2024 г. 14:32:36
     изяк осет
  2  Бекжан, 24 сентября 2022 г. 9:47:16
     разделяй и властвуй!
  3  Камалетдинов Гаяз Фаритович РИЛИ РБЛИ, 23 января 2022 г. 21:24:24
     https://stackoverflow.com/a/32729034
  4  Гнедов Андрей Александрович, 02 января 2022 г. 13:10:44
     На Питоне попробовал три способа решения: сортировка слиянием, сортировка по карманам, дерево Фенвика. Все три способа на тесте 10 дают TLE с почти одинаковым временем примерно 0,7 секунды. При этом среди полных решений очень много решений на Питоне, то есть в принципе решить на Питоне можно. Но как?
  5  АНТОНБЕК, 04 октября 2021 г. 15:20:27
     какой третий тест
  6  Тимофеев Кирилл Игоревич, 23 декабря 2020 г. 21:33:31
     Если у вас решение за O(n * k * log(n)), попробуйте ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); И другие оптимизации. У меня после того как поставил вышенаписанное, и поменял long long на int, зашло за 0.468)
  7  Матус Даниил Дмитриевич, 06 августа 2020 г. 1:00:42
     что за херня на обычном cin cout тл на 10 на freopenиз файла тоже но нет на сканэфе все прошло а так да корневая декомпозиция- разбиение большого массива на много маленьких размером с корень
  8  Кузнецов Степан Андреевич, 20 мая 2020 г. 19:23:43
     Изи Фенвик 0,124
  9  Ринчинов Солбон Геннадьевич, 08 мая 2020 г. 22:24:01
     У питона input().split() довольно медленный
  10  Кутузов Николай Владимирович, 01 мая 2020 г. 10:43:36
     Товарищи, я не могу понять: это проблема питона и его медленности, либо с алгоритмом что-то не так? Он вроде как имеет асимптотику O(k * n * log(n)), но на 10-ом тесте даёт TLE
  11  АЩщщ, 08 ноября 2019 г. 19:25:50
     Просто обычный Фенвик ,тут даже думать над алго не надо.
  12  Аркадий Сиплюсович, 20 октября 2019 г. 17:09:04
     легкая sqrt декомпозиция
  13  Винк В В, 17 марта 2018 г. 20:58:18
     В условии написано:"В каждом ряде". Так недалеко и до "ихнего" или "евошнего" )
  14  Иванов Иван, 20 сентября 2017 г. 0:41:17
     Одномерный фенвик -- TLE 10. Поставил scanf() -- зашла 0.186
  15  Монтеверде Авраам Соломонович, 22 июля 2017 г. 22:41:29
     В задаче не нужны никакие специфические структуры данных, кроме обычного массивчика, который можно сортировать (вектор).

Заметим, что если справа от солдата A находится M солдат, меньших А ростом, то при сортировке (так как все числа различны) ему так или иначе придётся пропустить этих М солдат слева от себя. На что это похоже? Правильно -- число инверсий для роста А в перестановке чисел от 1 до N.

Ну а для подсчёта числа инверсий в последовательности чисел давно используется merge_sort (сортировка слиянием) с небольшой модификацией. Итоговая ассимптотика решения -- k * n * log n, что по времени укладывается в 1 секунду. Моё решение работает 0.25 секунд максимум.

И не нужно тут никаких деревьев.
  16  Зубашев Степан, 07 августа 2016 г. 15:28:39
     Нашёл разбор. Понял главную свою ошибку. Можно решить гораздо компактнее и проще, если по-другому подходить к подсчёту кол-ва солдат выше ростом. Не важно что вы используете (скажем дерево отрезков, дерево Фенвика или же sqrt-декомпозицию). Ключ к простому решению: возможность обновления древа при просчёте результата слева направо. Подсчитали для I-го солдата, поправили древо, посчитали для I+1-го.
И тогда не нужны сортировки и бинарный поиск по сортированному массиву. Правда получилось всего в 1.5 раза быстрее :)
  17  Зубашев Степан, 04 августа 2016 г. 21:03:37
     Решил, используя:
1. дерево отрезков с подмассивами
2. сортировку слиянием (ввиду п.1)
3. бинарный поиск
Как-то уж больно лихо для 58%, не находите? Полагаю, что я сильно перемудрил. Можно было обойтись древом отрезков и без подмассивов? Судя по лучшим результатам ребята в 200 мс укладываются.
  18  Зубашев Степан, 04 августа 2016 г. 20:49:12
     Неожиданно для себя обнаружил, что моё решение не проходило из-за throw, который я использовал пока отлаживал своё решение. throw в коде остался, хотя и не использовался. Алгоритм работал. Но я уверенно получал TLE 1.3sec. Убрав неиспользуемый throw получил 0.5 sec. Нет я знал, что исключения это медленно, но я наивно полагал, что медленно отлавливать ошибки. Оказывается медленно всё. Для олимпиадных задач, похоже, совершенно не годится.
  19  Ислом Искандаров, 01 сентября 2015 г. 21:34:18
     Дерево отрезков !!! :)
  20  Керножицкий Александр Сергеевич, 19 мая 2015 г. 13:29:22
     Дерево Фенвика!!!
 1 2 3

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ICQ: 151483, E-mail: admin@acmp.ru