Submission #1129796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129796		not_amir	Escape Route 2 (JOI24_escape2)	C++20	54 / 100	3095 ms	23576 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());
        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);
    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;
    }
    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};
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        ll mina = LONG_MAX;
        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);
        }
        cout << mina << '\n';
    }
}

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