acmp_1513.cpp

#include <stdio.h>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdint>

struct Worker {
    int ts, floor; // Время вызова, этаж
    int64_t tf; // Время высадки на первый этаж (ответ)

    Worker(int time_start = 0, int floor = 0, int64_t time_finish = -1)
        : ts(time_start)
        , floor(floor)
        , tf(time_finish)
    { }
};

int main () {
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);

    int nWorkers, nFloors;
    scanf("%d %d", &nWorkers, &nFloors);

    // Читаем входные данные и заносим их в вектор:
    std::vector<Worker> workers;
    for (int i = 0; i < nWorkers; ++i) {
        int time, floor;
        scanf("%d %d", &time, &floor);
        workers.push_back(Worker(time, floor));
    }

    // Очередь ожидающих обработки рабочих: wait[этаж] --> список рабочих, ожидающих лифта
    std::map<int, std::vector<int>> wait;

    int firstNotFinished = 0; // Первый не обработанный
    int firstNotWait = 0;     // Первый не оижадющий обработки
    int64_t curr_time = 0;    // Текущее время
    while (firstNotFinished < nWorkers) {
        // Пропускаем всех тех, кого уже обработали:
        if (workers[firstNotFinished].tf != -1) {
            ++firstNotFinished;
            continue;
        }

        // Получаем информацию о текущем активном вызове:
        int64_t currWorkerTime  = workers[firstNotFinished].ts;
        int64_t currWorkerFloor = workers[firstNotFinished].floor;

        // Добавляем первого необработанного в очередь:
        if (firstNotFinished > firstNotWait) {
            wait[currWorkerFloor].push_back(firstNotFinished);
            if (firstNotFinished == firstNotWait) {
                ++firstNotWait;
            }
        }

        // Текущее время старта и время окончания:
        curr_time = std::max(curr_time, currWorkerTime);
        int64_t finish_time = curr_time + 2 * (currWorkerFloor - 1);

        // Обрабатываем тех, которые уже ожидают на этажах:
        auto it = wait.begin();
        while (it != wait.end()) { // Пробегаем все этажи до активного включительно
            if (it->first > currWorkerFloor) { // Вышли за пределы активного этажа - выходим
                break;
            }
            for (const auto w : it->second) { // Забираем всех тех, которые ожидают в данный момент:
                workers[w].tf = finish_time;
            }
            // Переходим к следующей итерации, подчищая за собой мусор:
            wait.erase(it++);
        }

        // Обрабатываем тех, которые вызывают лифт в тот промежуток времени, когда лифт движется вверх-вниз:
        while (firstNotWait < nWorkers) {
            if (workers[firstNotWait].ts > finish_time) {
                // Лифт завершит движение вверх-вниз раньше, чем придет текущий работник - выходим
                break;
            }

            if (
                workers[firstNotWait].floor > currWorkerFloor || // Работник вызывает лифт на этаже выше активного этажа, до которого поднимается лифт
                workers[firstNotWait].floor + workers[firstNotWait].ts > currWorkerFloor + (finish_time + curr_time) / 2 // Работник не успевает на лифт
            ) {
                // Вносим работника в список ожидающих:
                wait[workers[firstNotWait].floor].push_back(firstNotWait);
            } else {
                // Иначе работник успевает на лифт:
                workers[firstNotWait].tf = finish_time;
            }
            ++firstNotWait;
        }

        // Лифт закончил движение вверх-вниз:
        curr_time = finish_time;
    }

    // Выводим ответ:
    for (auto & w : workers) {
        printf("%I64d\n", w.tf);
    }

    return 0;
}