АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

13. Инверсии

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Дана последовательность неповторяющихся целых чисел. Инверсией назовём такую ситуацию, когда большее число стоит впереди меньшего. Например, в последовательности 4 3 2 5 1 всего 7 инверсий: 4 и 3, 4 и 2, 4 и 1, 3 и 2, 3 и 1, 2 и 1, 5 и 1. Задача: определить количество инверсий в последовательности.

Исходные данные

В первой строке записано целое N - длина последовательности (1<=N<=50000 ). В следующей строке через пробел записаны N неповторяющихся целых чисел - члены последовательности. Каждое число лежит в диапазоне от 1 до 1000000.

Результат

Выведите одно целое число - количество инверсий.

Пример

Исходные данныеРезультат
5
4 3 2 5 1
7

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи по темам / Математика / Комбинаторика /
873. Tower of Hanoi 13. 1563. Лампочки
Задачи с соревнований / Отборочные туры ВоГУ / Отборочный тур на ACM ICPC 2004 /
13. 14. B - Выражение 15. C - Факториалы 16. D - Многоугольник
Учебные курсы / Структуры и алгоритмы / Сортировка данных и смежные темы /
4. Быстрая сортировка 13. 659. Отсортируйте список
 
время генерации 0.078 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.