Что спрашивают

У продукта два срока. Все 2N сроков просматривают по возрастанию. При первом появлении продукта его ставят на первое свободное место с начала, если это срок хранения, или с конца, если это срок после вскрытия. Повторное появление пропускают.

Найдите номер последнего размещённого продукта и число продуктов ниже него. N ≤ 1000, сроки ≤ 10^9, все 2N значений различны. Номера продуктов задаёт исходный порядок строк.

Приём решения

Создадим два события для каждого продукта: (срок, сторона, индекс), где сторона 0 означает начало рейтинга, 1 — конец. Отсортируем события по сроку. Массив used отметит продукты, которые уже получили место.

Свободные позиции всегда составляют сплошной отрезок: размещение забирает только левый или правый край. Поэтому весь рейтинг хранить не требуется, достаточно указателей left и right. Для события неиспользованного продукта занимаем нужный край, двигаем соответствующий указатель и запоминаем номер и позицию.

Последнее успешное размещение определяет ответ. Если его позиция position считается с нуля, ниже находятся N - 1 - position продуктов. Номер продукта равен исходному индексу плюс один и не связан с его местом.

Просмотр второго срока уже размещённого продукта не меняет ни края, ни последний ответ. Время O(N log N), память O(N) на события и отметки.

Разбор на примере

Ввод

4
7 2
1 8
6 5
3 9

Вывод

3 1
Разбор примера по шагам
СрокПродукт / сторонаЗанятое место
12, с начала1
21, с конца4
34, с начала2
53, с конца3; последнее размещение
6, 7, 8, 9Повторные событияПропускаем

Срок 1 ставит продукт 2 в начало. Срок 2 ставит продукт 1 в конец. Срок 3 размещает продукт 4 на втором месте, срок 5 — продукт 3 на третьем. Остальные сроки относятся к уже размещённым продуктам. Итоговый рейтинг 2, 4, 3, 1: последним размещён продукт 3, ниже него один продукт.

Код на Python и C++

Различность всех сроков исключает неоднозначность одновременных событий. Нулевое число продуктов ниже последнего размещённого допустимо.

В C++ события — tuple<long long, int, int>, и sort сравнивает их так же, как кортежи в Python.

import sys


def solve(products):
    n = len(products)
    events = sorted((value, side, i)
                    for i, pair in enumerate(products)
                    for side, value in enumerate(pair))
    used = [False] * n
    left, right = 0, n - 1
    last = position = 0
    for value, side, i in events:
        if used[i]:
            continue
        used[i] = True
        last = i + 1
        if side == 0:
            position = left
            left += 1
        else:
            position = right
            right -= 1
    return last, n - 1 - position


if __name__ == '__main__':
    data = list(map(int, sys.stdin.buffer.read().split()))
    products = list(zip(data[1::2], data[2::2]))
    print(*solve(products))
#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    // События (срок, сторона, индекс): сторона 0 — левый срок продукта, 1 — правый.
    vector<tuple<long long, int, int>> events;
    for (int i = 0; i < n; i++) {
        long long first, second;
        cin >> first >> second;
        events.push_back({first, 0, i});
        events.push_back({second, 1, i});
    }
    sort(events.begin(), events.end());
    vector<bool> used(n, false);
    int left = 0, right = n - 1;
    int last = 0, position = 0;
    for (auto [value, side, i] : events) {
        if (used[i])
            continue;
        used[i] = true;
        last = i + 1;
        if (side == 0) {
            position = left;
            left += 1;
        } else {
            position = right;
            right -= 1;
        }
    }
    cout << last << ' ' << n - 1 - position << endl;
}

Типичные ошибки

  • Разместить продукт дважды

    После первого события used[i] становится True. Его второй срок уже ничего не делает.

  • Вывести последнюю строку входа

    Порядок размещения задаётся сроками, а идентификатор сохраняется из исходной нумерации.

  • Вывести position как число стоящих ниже

    Позиция отсчитывается от начала. Ниже находятся N - 1 - position, а не position продуктов.