Problem A. Lin-log sort

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that receives a sequence of integer numbers and sorts it, i. e. writes out all elements in ascending order.

Input file format

Input file contains integer N — length of the sequnece, followed by N integer numbers — elements of the sequence.

Output file format

Output file must contain N integer numbers, which must be elements of the source sequence printed in ascending order.

Constraints

0 ≤ N ≤ 100000. Sequence elements are less than 109 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4 3 10 3 1
1 3 3 4 10

Задача B. Передовики производства

Автор:folklore   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

На секретном оборонном заводе трудятся N рабочих. Каждый рабочий характеризуется своей производительностью — целым числом. С течением времени производительность некоторых рабочих может увеличиваться или уменьшаться. Вам задано число M — количество изменений производительности. Для каждого изменения известен номер рабочего, изменившего свою производительность и значение, на которое он она изменилась. Величина изменения может быть как положительной, так и отрицательной. Для планирования будущих достижений руководству завода необходимо всегда знать наибольшую производительность, достигнутую рабочими в данный момент.

Формат входного файла

В первой строке входного файла содержатся целые числа N M, разделенные пробелами. Далее следуют N чисел Ai, обозначающих производительность i-рабочего. Завершают входной файл M пар чисел Numi Vali, обозначающие номер рабочего, производительность которого изменилась и величину изменения соответственно.

Формат выходного файла

В выходной файл необходимо вывести M чисел — после каждого изменения производительности необходимо вывести наибольшую производительность по заводу.

Ограничения

(1 ≤ N, M ≤ 100000, 1 ≤ NumiN, −1000 ≤ Vali, Ai ≤ 1000)

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 4
7 4 9 
2 3
1 4
2 10
2 -10
9
11
17
11

Задача C. Количество инверсий последовательнсти

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Пара элементов (Ai, Aj) последовательности AN называется инверсией, если Ai > Aj и i < j.

Напишите программу, которая по заданной последовательности AN посчитает количество инверсий.

Формат входного файла

В первой строке входного файла содержится число N — количество элементов последовательности

Последующие N целых чисел задают саму последовательность

Формат выходного файла

В выходном файле должно содержаться единственное число — количество инверсий входной последовательности.

Ограничения

2 ≤ N ≤ 105

0 ≤ Ai ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
7 1 2 5 9 13 16 20
0
2
9
1 1 2 3 8 6 1 9 9
5

Задача D. K-ая порядковая статистика

Автор:StdAlg   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

K-ой порядковой статистикой N-элементной последовательности AN называется число AK, которое будет стоять на K-ом месте после упорядочивания элементов этой последовательности по возрастанию.

Последовательность AN задаётся следующим образом. A1 = P, Ai = (Ai − 1 ⋅ Q) mod V.

Формат входного файла

Во входном файле содержатся целые числа Q V P N K

Формат выходного файла

В выходном файле должно содержаться единственное число — K-ая порядковая статистика исходной последовательности.

Ограничения

V, Q ≠ 0

0 ≤ Q ⋅ V, Q ⋅ P ≤ 231 − 1

1 ≤ K ≤ N ≤ 4 ⋅ 107

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
343 32767 3 10 7
16478

Задача E. Результаты квалификации

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Перед началом шоссейно-кольцевых автомобильных гонок проводится квалификация, результаты которой определяют расположение автомобилей на старте гонки.

Во время квалификации каждый гонщик может проехать неограниченное число кругов, и минимальное время, за которое гонщик смог проехать круг, называется его лучшим временем.

Затем на старте гонки гонщики сортируются по возрастанию лучшего времени, в случае его равенства впереди будет тот, кто показал это время раньше.

Когда гонщик завершает очередной круг, в журнал записываются числа Bi и Ti — номер его машины и разность между временем, за которое он проехал этот круг, и текущим лучшим среди всех гонщиков временем. (Ti измеряется в тысячных долях секунды, T1 всегда равно 0). Если Ti < 0, то время, показанное этим гонщиком, становится лучшим.

Требуется определить результат квалификации по записям в журнале.

Формат входного файла

Входной файл содержит число N — общее количество кругов, сделанных всеми гонщиками в квалификации.

Далее содержатся N пар целых чисел Bi Ti — записи в журнале в хронологическом порядке.

Формат выходного файла

Выходной файл должен содержать номера гоночных автомобилей, перечисленные в порядке расположения на старте гонки.

Ограничения

1 ≤ N ≤ 105

Разница между лучшим и худшим временем не превышает 109 тысячных секунды

1 ≤ Bi ≤ 106

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
6
7
+0
2
+123
5
-11
2
+7
1
+0
3
+60200
5 1 2 7 3

Задача F. Финишные позиции

Автор:А. Жуплев   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

На одном из этапов марсианских гонок по кольцевому треку вышла из строя программа, рассчитывающая финишные позиции гонщиков. На трассе имеется специальное оборудование, формирующее хронику гонки — список машин, пересекающих финишную черту. То есть, когда машина заканчивает очередной круг, пересекая финишную черту, её номер добавляется в список. Например, если список имеет вид 4 7 8 7 4 8 7 4, то это означает, что первый круг закончили машины с номерами 4 7 8 в указанном порядке, на втором круге машина 7 обогнала машину 4, а на третий круг закончили только машины 7 4, а машина 8 либо сломалась, либо всё ещё находится на втором круге.

Требуется написать программу, которая по заданному списку машин определит их финишные позиции.

По правилам марсианских кольцевых гонок гонщики, проехавшие большее количество кругов находятся на более высоких позициях, чем те, которые проехали меньшее. В группе гонщиков, проехавших одинаковое количество кругов, более высокую позицию занимает тот, кто раньше пересёк финишную черту.

Формат входного файла

Во входном файле содержится число N — количество элементов списка.

Далее следуют N чисел, задающие список.

Формат выходного файла

В выходном файле должны содержаться номера машин в том порядке, в котором они финишировали в гонке.

Ограничения

1 ≤ N ≤ 106

Номера машин являются целыми неотрицательными числами, не превосходящими 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
5 1 10
5 1 10
2
8
4 7 8 7 4 8 7 4
7 4 8
3
16
17 88 39 88 17 39 88 17 88 17 39 39 17 39 17 222222222
17 39 88 222222222

0.542s 0.030s 23