CS
Задачник Базовый курс EN

Задача

Миллион температур

замеры массив потоковая обработка

Метеостанция записывает среднюю температуру каждого дня в десятых долях градуса. День — рекорд жары, если он теплее всех предыдущих, и рекорд холода, если холоднее всех предыдущих; первый день считается и тем и другим.

Сколько было рекордов жары, сколько рекордов холода и каким по счёту был последний рекорд жары?

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

Вход

В первой строке n (1 ≤ n ≤ 10⁶). Дальше n строк по одному целому числу от −600 до 600 — температура дня в десятых долях градуса.

Выход

Три числа: число рекордов жары, число рекордов холода и номер последнего дня-рекорда жары (дни нумеруются с единицы).

Примеры

Пример 1

Вход
8
-52
-31
-80
12
12
40
-95
38
Выход
4 3 6

Ограничения

Время · Python
1000 мс
Время · Go
500 мс
Память
256 МБ
Проверка
6 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Алгоритм здесь — один проход с текущими максимумом и минимумом. Посчитайте, сколько раз программа обращается ко вводу, и сколько стоит каждое обращение.

2Идея

Прочитать весь вход одним вызовом и разрезать по пробелам: в Python — sys.stdin.buffer.read().split(), в Go — буферизованный bufio.Reader и разбор чисел вручную. Дальше обычный цикл.

3Разбор

Решение с int(input()) на каждую строку верное, но на миллионе дней не успевает. Каждый вызов input() спрашивает у стандартного ввода номер файла, проверяет, не терминал ли это, и сбрасывает буферы вывода и ошибок — и только потом читает строку. Чтение всего сразу делает одно обращение к системе на мегабайт и одно разрезание. Почему так и сколько это стоит в Python и в Go, разобрано в статье «Быстрый ввод и вывод».

В Go ловушка другая: fmt.Scan прямо из os.Stdin делает по системному вызову на каждый байт входа, а это несколько миллионов вызовов. Достаточно обернуть ввод в bufio.NewReader, а ещё быстрее — читать числа из буфера по байту, как в эталонном решении.

Пятый тест — настоящие 85 лет погоды Алматы по реанализу: 31 рекорд жары, последний — 9 августа 1944 года, тот самый день, который в статье о монотонном стеке так и не дождался более тёплого.

3+Решение
4Сложность

O(n) по времени. Чтение всего сразу держит в памяти весь вход — несколько мегабайт, это допустимо; при гигабайтах читали бы кусками.

5Типичные ошибки
  • input() на каждую строку. Верно, но медленно на шестом тесте.
  • fmt.Scan без буфера в Go. Системный вызов на каждый байт.
  • Нестрогое сравнение. День, равный рекорду, рекордом не считается — третий тест из одинаковых дней.

Алгоритмы задачи

TEC Приём Быстрый ввод и вывод Миллион чисел за десятки миллисекунд вместо секунды: чтение целиком, буфер и одна запись вывода. O(размер входа) 1 задача TEC Приём Префиксные суммы Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки. O(n) на построение, O(1) на запрос 2 задачи
Каталог алгоритмов