Submission #1240211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240211		rythm_of_knight	Escape Route 2 (JOI24_escape2)	C++17	100 / 100	749 ms	247456 KiB

Main

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ar array
using namespace std;
typedef long long ll;

const int N = 1e5 + 5, K = 200;
ar <ll, 2> g[N], st[17][N];
ll prec[N / K + 3][N], prans[N / K + 3][N];
int id[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, t, f = 1;
    cin >> n >> t;
    vector <vector <ar <int, 3>>> a(n + 1), b(n + 1);
    for (int i = 1; i < n; i++) {
        int m;
        cin >> m;
        a[i].resize(m);
        b[i].resize(m);
        int mb = t, wh = -1;
        for (int j = 0; j < m; j++) {
            cin >> a[i][j][0] >> a[i][j][1];
            a[i][j][2] = b[i][j][2] = f++;
            if (mb > a[i][j][1]) {
                mb = a[i][j][1];
                wh = a[i][j][2];
            }
            b[i][j][0] = a[i][j][1];
            b[i][j][1] = a[i][j][0];
        }
        sort(all(a[i]));
        vector <ar <int, 2>> sf(m);
        int mn = t, wmn = -1;
        for (int j = m - 1; j >= 0; j--) {
            if (mn > a[i][j][1]) {
                mn = a[i][j][1];
                wmn = a[i][j][2];
            }
            sf[j] = {mn, wmn};
        }
        if (i > 1) {
            int j = i - 1;
            for (auto now : a[j]) {
                int k = lower_bound(all(a[i]), ar <int, 3>({now[1], -1, -1})) - a[i].begin();
                if (k < m) {
                    g[now[2]] = {sf[k][1], sf[k][0] - now[1]};
                } else {
                    g[now[2]] = {wh, mb + t - now[1]};
                }
            }
        }
    }
    for (int i = 1; i < f; i++)
        st[0][i] = g[i];
    for (int i = 1; i < 17; i++) {
        for (int j = 1; j < f; j++) {
            st[i][j] = st[i - 1][st[i - 1][j][0]];
            st[i][j][1] += st[i - 1][j][1];
        }
    }
    int tmpp = 1;
    for (int i = 1; i < n; i++) {
        if (a[i].size() >= K) {
            id[i] = tmpp++;
            int ed = id[i];
            for (int j = 1; j < f; j++)
                prec[ed][j] = 1e18;
            for (auto now : a[i])
                prec[ed][now[2]] = now[1] - now[0];
            for (int j = i; j < n; j++) {
                ll mn = 1e18;
                for (auto now : a[j]) {
                    mn = min(mn, prec[ed][now[2]]);
                    int nxt = g[now[2]][0];
                    prec[ed][nxt] = min(prec[ed][nxt], prec[ed][now[2]] + g[now[2]][1]);
                }
                prans[ed][j + 1] = mn;
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        if (a[l].size() >= K) {
            cout << prans[id[l]][r] << '\n';
        } else {
            ll ans = 1e18;
            for (auto now : a[l]) {
                ll res = now[1] - now[0];
                int dis = r - l - 1, b = 0, x = now[2];
                while (dis) {
                    if (dis & 1) {
                        res += st[b][x][1];
                        x = st[b][x][0];
                    }
                    b++, dis >>= 1;
                }
                ans = min(ans, res);
            }
            cout << ans << '\n';
        }
    }
}
/*
4 10000
3
400 500
500 501
100 300
3
100 800
200 400
300 600
1
500 600
3
1 3
2 4
1 4
*/

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