Submission #1129819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129819		not_amir	Escape Route 2 (JOI24_escape2)	C++20	100 / 100	2538 ms	55780 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, ll> pii;

int main() {
    cin.tie(nullptr);
    int n;
    ll t;
    cin >> n >> t;
    vector<vector<pii>> ranges(n - 1);
    for (int i = 0; i < n - 1; i++) {
        int m;
        cin >> m;
        vector<pii> tmp(m);
        for (auto& [A, B] : tmp)
            cin >> A >> B;
        sort(tmp.begin(), tmp.end(), [](const pii& x, const pii& y) {
            if (x.second == y.second)
                return x.first > y.first;
            return x.second < y.second;
        });
        int mx = -1;
        for (auto& [A, B] : tmp) {
            if (A <= mx)
                continue;
            mx = A;
            ranges[i].push_back({A, B});
        }
        reverse(ranges[i].begin(), ranges[i].end());
    }
    vector<int> dpthf, dpthr;
    vector<pii> jmpf, jmpr, nxtf, nxtr;
    vector<int> idxf, idxr;
    vector<pii> prev;
    vector<vector<int>> endf(n), endr(n);
    for (int i = 1, cnt = 0; i < n; i++) {
        vector<int> cidx, ends;
        vector<pii> tmp;
        for (int j = 0; j < ranges[i - 1].size(); j++) {
            auto [A, B] = ranges[i - 1][j];
            cidx.push_back(cnt);
            idxf.push_back(i - 1);
            nxtf.push_back({cnt, 0});
            cnt++;
            idxf.push_back(i);
            nxtf.push_back({cnt - 1, B - A});
            tmp.push_back({B, cnt});
            ends.push_back(cnt);
            cnt++;
        }
        endf[i] = ends;
        if (!prev.empty()) {
            bool cycled = false;
            for (int j = 0, it = 0; j < ranges[i - 1].size(); j++) {
                auto [A, B] = ranges[i - 1][j];
                while (!cycled && prev[it].first > A) {
                    if (it == prev.size() - 1) {
                        it = 0;
                        cycled = true;
                    }
                    else
                        it++;
                }
                nxtf[cidx[j]] = {prev[it].second, (A - prev[it].first + t) % t};
            }
        }
        prev = tmp;
    }

    prev.clear();
    for (int i = n - 2, cnt = 0; i >= 0; i--) {
        vector<int> cidx, ends;
        vector<pii> tmp;
        reverse(ranges[i].begin(), ranges[i].end());
        for (int j = 0; j < ranges[i].size(); j++) {
            auto [A, B] = ranges[i][j];
            cidx.push_back(cnt);
            idxr.push_back(i + 1);
            nxtr.push_back({cnt, 0});
            cnt++;
            idxr.push_back(i);
            nxtr.push_back({cnt - 1, B - A});
            tmp.push_back({A, cnt});
            ends.push_back(cnt);
            cnt++;
        }
        endr[i] = ends;
        if (!prev.empty()) {
            bool cycled = false;
            for (int j = 0, it = 0; j < ranges[i].size(); j++) {
                auto [A, B] = ranges[i][j];
                while (!cycled && prev[it].first < B) {
                    if (it == prev.size() - 1) {
                        it = 0;
                        cycled = true;
                    }
                    else
                        it++;
                }
                nxtr[cidx[j]] = {prev[it].second, (prev[it].first - B + t) % t};
            }
        }
        prev = tmp;
    }

    jmpf.resize(idxf.size());
    dpthf.resize(idxf.size(), 0);
    for (int i = 0; i < idxf.size(); i++) {
        auto [p, w] = nxtf[i];
        if (p == i)
            jmpf[i] = {i, 0};
        else {
            dpthf[i] = dpthf[p] + 1;
            if (dpthf[jmpf[p].first] - dpthf[p] == dpthf[jmpf[jmpf[p].first].first] - dpthf[jmpf[p].first])
                jmpf[i] = {jmpf[jmpf[p].first].first, jmpf[p].second + jmpf[jmpf[p].first].second + w};
            else
                jmpf[i] = {p, w};
        }
    }

    jmpr.resize(idxr.size());
    dpthr.resize(idxr.size(), 0);
    for (int i = 0; i < idxr.size(); i++) {
        auto [p, w] = nxtr[i];
        if (p == i)
            jmpr[i] = {i, 0};
        else {
            dpthr[i] = dpthr[p] + 1;
            if (dpthr[jmpr[p].first] - dpthr[p] == dpthr[jmpr[jmpr[p].first].first] - dpthr[jmpr[p].first])
                jmpr[i] = {jmpr[jmpr[p].first].first, jmpr[p].second + jmpr[jmpr[p].first].second + w};
            else
                jmpr[i] = {p, w};
        }
    }

    int q;
    cin >> q;
    map<pii, ll> mp;
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        if (mp.count({l, r})) {
            cout << mp[{l, r}] << '\n';
            continue;
        }
        ll mina = LONG_MAX;
        if (endr[l].size() > endf[r].size()) {
            for (int v : endf[r]) {
                ll sm = 0;
                while (idxf[v] > l) {
                    if (idxf[jmpf[v].first] > l) {
                        sm += jmpf[v].second;
                        v = jmpf[v].first;
                    }
                    else {
                        sm += nxtf[v].second;
                        v = nxtf[v].first;
                    }
                }
                mina = min(mina, sm);
            }
        }
        else {
            for (int v : endr[l]) {
                ll sm = 0;
                while (idxr[v] < r) {
                    if (idxr[jmpr[v].first] < r) {
                        sm += jmpr[v].second;
                        v = jmpr[v].first;
                    }
                    else {
                        sm += nxtr[v].second;
                        v = nxtr[v].first;
                    }
                }
                mina = min(mina, sm);
            }
        }
        mp[{l, r}] = mina;
        cout << mina << '\n';
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 17 / 17
• Subtask 4: 23 / 23
• Subtask 5: 36 / 36
• Subtask 6: 10 / 10