Задача A. Быстрый Дейкстра ≡

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

Условие

Вам необходимо написать программу, которая получает взвешенный ориентированный граф и находит в нем расстояния от вершины S до всех остальных вершин. Расстояние от вершины S до некоторой вершины W — это минимальная длина пути из S в W. Длина пути — это сумма весов всех рёбер, входящих в него.

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

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

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

Выходной файл должен содержать N чисел. Каждое I-е число — это расстояние от вершины до S до вершины I. Если некоторые вершины недостижимы из S, то для для них должно быть выведено −1.

Ограничения

1 ≤ N, M ≤ 100000 Все веса меньше или равны 1000.

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

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

Задача B. Задание котёнку ≡

Автор:Жюри зимних сборов 2005
Входной файл: kitten.in   Ограничение времени:2 сек
Выходной файл: kitten.out   Ограничение памяти:64 Мб

Условие

Маленький котёнок заблудился в лабиринте. Дни и ночи он плутал, совсем обессилев, пока не наткнулся на Бабу-Ягу. Баба-Яга сначала хотела съесть котёнка, но потом передумала, увидев, что от него остались кожа да кости. Но котёнок все мяукал и мяукал, а топить его противно — воды Баба-Яга боится! Поэтому-то Баба-Яга и решила спровадить бедного котёнка, дав ему подробную карту лабиринта — все равно эта карта только место занимает!

Но не в правилах злодеев делать что-то, особенно доброе, просто так. Поэтому Баба-Яга дала задание котёнку — вести учет вызванных чертей. Баба-Яга хочет построить чертей в шеренгу. Шеренга будет расположена на прямой, причем черти вызываются в целых точках этой прямой. Если в какой-то точке прямой чёрт уже призван, то повторный призыв чёрта не изменяет состояния этой точки, иначе эта клетка заполняется чёртом.

Бабе-Яге очень приятно восхищаться чёрным делом рук своих, и она хочет периодически задавть вопросы: а сколько, собственно, чертей находится на заданном отрезке? И этой грязной работой должен заниматься котёнок, пока Бабе-Яге не надоест. Но это его единственный шанс выбраться из лабиринта!

Помогите котёнку написать программу, которая по заданной последовательности запросов Бабы-Яги и вызовов чертей ответит на каждый запрос.

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

Входной файл состоит из запросов Бабы-Яги и вызовов чертей. События происходят в том порядке, в котором они описаны во входном файле. Если соответствующая строка содержит одно число Ai, то оно соответствует вызову чёрта в позицию Ai. Иначе в строке содержится два числа Ai и Bi, которые означают, что Баба-Яга пожелала узнать, сколько же чертей заключено между точками с координатами между Ai и Bi?

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

Для каждого из запросов Бабы-Яги в отдельной строке необходимо вывести число — ответ на запрос.

Ограничения

Запросов во входном файле не более 200000, все числа Ai и Bi по модулю не превосходят 106. Последняя строка входного файла обязательно завершается переводом строки.

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

№ Входной файл (kitten.in) Выходной файл (kitten.out)
1 
2 3
5
2 6
5 6
7 8
9
3 9
5
3 9
 
0
1
1
0
2
2

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

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

Условие

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

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

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

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

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

Ограничения

(1 ≤ N, M ≤ 100000, 1 ≤ Numi ≤ N, −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
0.039s 0.006s 11