Submission #1342535

#TimeUsernameProblemLanguageResultExecution timeMemory
1342535MisterReaperEscape Route 2 (JOI24_escape2)C++20
100 / 100
459 ms126960 KiB
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

template<typename T>
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr i64 inf = i64(1E18);
constexpr int max_N = int(1E5) + 5;
constexpr int max_Q = int(3E5) + 5;
constexpr int LG = std::__lg(max_N) + 1;
constexpr int B = int(std::sqrt(max_N / LG));

int N;
int T;
int M[max_N];
std::vector<std::array<int, 2>> all;
std::vector<std::array<int, 2>> to[max_N];
std::vector<std::array<int, 2>> lift[LG];

int imp[max_N];
std::vector<i64> anses[(max_N + B - 1) / B];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N >> T;

    for (int i = 1; i < N; ++i) {
        std::cin >> M[i];
        to[i].resize(M[i]);
        for (int j = 0; j < M[i]; ++j) {
            std::cin >> to[i][j][0] >> to[i][j][1];
        }
        std::sort(to[i].begin(), to[i].end());
        std::vector<std::array<int, 2>> stk;
        for (int j = 0; j < M[i]; ++j) {
            while (!stk.empty() && stk.back()[1] >= to[i][j][1]) {
                stk.pop_back();
            }
            stk.emplace_back(to[i][j]);
        }
        to[i] = std::move(stk);
        M[i] = int(to[i].size());
        all.insert(all.end(), to[i].begin(), to[i].end());
    }

    std::vector<int> ps(N + 1);
    for (int i = 1; i < N; ++i) {
        ps[i + 1] = ps[i] + int(to[i].size());
    }

    lift[0].resize(ps[N]);
    for (int i = 1; i < N - 1; ++i) {
        for (int j = 0; j < M[i]; ++j) {
            int p = int(std::lower_bound(to[i + 1].begin(), to[i + 1].end(), std::array<int, 2>{to[i][j][1], -1}) - to[i + 1].begin());
            if (p == M[i + 1]) {
                lift[0][ps[i] + j] = {ps[i + 1] + 0, 1};
            } else {
                lift[0][ps[i] + j] = {ps[i + 1] + p, 0};
            }
        }
    }
    for (int j = 0; j < M[N - 1]; ++j) {
        lift[0][ps[N - 1] + j] = {-1, -1};
    }

    for (int i = 1; i < LG; ++i) {
        lift[i].resize(ps[N]);
        for (int j = 0; j < ps[N]; ++j) {
            auto[x, y] = lift[i - 1][j];
            if (x == -1) {
                lift[i][j] = {-1, -1}; 
            } else {
                auto[x1, y1] = lift[i - 1][x];
                lift[i][j] = {x1, y + y1};
            }
        }
    }

    auto answer = [&](int v, int dt) -> i64 {
        int d = 0;
        int st = all[v][0];
        for (int i = LG - 1; i >= 0; --i) {
            if (dt >> i & 1) {
                d += lift[i][v][1];
                v = lift[i][v][0];
            }
        }
        int en = all[v][1];
        debug(en, st, d);
        return en - st + 1LL * d * T;
    };

    for (int i = 1; i < N; ++i) {
        if (M[i] > B) {
            imp[i] = ++imp[0];
            anses[imp[i]].resize(N + 1, inf);
            std::vector<i64> dis(ps[N], inf);
            for (int j = 0; j < M[i]; ++j) {
                dis[ps[i] + j] = 0;
            }
            for (int j = i; j < N; ++j) {
                for (int k = 0; k < M[j]; ++k) {
                    debug(ps[j] + k, dis[ps[j] + k], to[j][k]);
                    chmin(anses[imp[i]][j + 1], dis[ps[j] + k] + to[j][k][1] - to[j][k][0]);
                    if (j != N - 1) {
                        chmin(dis[lift[0][ps[j] + k][0]], dis[ps[j] + k] + all[lift[0][ps[j] + k][0]][0] - to[j][k][0] + lift[0][ps[j] + k][1] * T);
                    }
                }
            }
            debug(dis);
            debug(anses[imp[i]]);
        }
    }

    int Q;
    std::cin >> Q;

    while (Q--) {
        int L, R;
        std::cin >> L >> R;
        if (imp[L]) {
            i64 res = anses[imp[L]][R];
            std::cout << res << '\n';
        } else {
            i64 mn = inf;
            for (int j = 0; j < M[L]; ++j) {
                chmin(mn, answer(ps[L] + j, R - L - 1));
            }
            std::cout << mn << '\n';
        }
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...