Submission #1127904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127904		antonn	Escape Route 2 (JOI24_escape2)	C++20	54 / 100	3095 ms	59764 KiB

Main

#include <bits/stdc++.h>
 
 
using namespace std;
 
 
#define ll long long
#define ld long double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 

int n, T, q;
vector<vector<int>> g;
vector<vector<int>> anc, f;
vector<vector<ll>> t;
vector<int> dep;
vector<int> A, B;


void dfs(int u, int p = 0) {
    anc[0][u] = p; 
    for (auto v : g[u]) {
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}


ll join(ll t1, ll t2, int x, int y) {
    if (B[x] <= A[y]) {
        return t1 + A[y] - B[x] + t2;
    } else {
        return t1 + T - B[x] + A[y] + t2;
    }
}


int get(int x, int k) {
    for (int h = 19; h >= 0; h -= 1) {
        if (k & (1 << h)) {
            x = anc[h][x];
        }
    }
    return x;
}


ll lift(int a, int k) {
    ll ans = 0;
    int b = a;
    for (int h = 19; h >= 0; h -= 1) {
        if (k & (1 << h)) {
            if (ans == 0) {
                ans = t[h][a];
            } else {
                ans = join(ans, t[h][a], b, a);
            }
            b = f[h][a];
            a = anc[h][a];
        }
    }
    return ans;
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
	}
    cin >> n >> T;
    vector<int> m(n + 1);
    vector<vector<pair<int, int>>> a(n + 1);
    for (int i = 1; i <= n - 1; i += 1) {
        cin >> m[i];
        a[i].resize(m[i]);
        for (int j = 0; j < m[i]; j += 1) {
            cin >> a[i][j].first >> a[i][j].second;
        }
        sort(all(a[i]));
    }
    m[n] = 1;
    a[n].push_back({T, T}); 
    vector<int> sum(n + 1);
    for (int i = 1; i <= n; i += 1) {
        sum[i] = sum[i - 1] + m[i];
    }
    auto get_id = [&](int i, int j) {
        return sum[i - 1] + j + 1;
    };

    vector<vector<pair<int, int>>> suff(n + 1);
    for (int i = 1; i <= n; i += 1) {
        suff[i].resize(m[i]);
        suff[i][m[i] - 1] = {a[i][m[i] - 1].second, m[i] - 1};
        for (int j = m[i] - 2; j >= 0; j -= 1) {
            suff[i][j] = min(suff[i][j + 1], {a[i][j].second, j}); 
        }
    }
    g.resize(sum[n] + 1);
    for (int i = 1; i <= n - 1; i += 1) {
        for (int j = 0; j < m[i]; j += 1) {
            int A = a[i][j].first;
            int B = a[i][j].second;
            int l = 0, r = m[i + 1] - 1, sol = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (a[i + 1][mid].first >= B) {
                    sol = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if (sol == -1) {
                g[get_id(i + 1, suff[i + 1][0].second)].push_back(get_id(i, j));
            } else if (sol != -1) {
                g[get_id(i + 1, suff[i + 1][sol].second)].push_back(get_id(i, j));
            }
        }
    }
    dep.resize(sum[n] + 1);
    anc.assign(20, vector<int>(sum[n] + 1));
    f.assign(20, vector<int>(sum[n] + 1));
    t.assign(20, vector<ll>(sum[n] + 1));
    dfs(sum[n]);
    A.resize(sum[n] + 1);
    B.resize(sum[n] + 1);
    for (int i = 1; i <= n; i += 1) {
        for (int j = 0; j < m[i]; j += 1) {
            t[0][get_id(i, j)] = a[i][j].second - a[i][j].first; 
            A[get_id(i, j)] = a[i][j].first;
            B[get_id(i, j)] = a[i][j].second;
        }
    }
    for (int h = 1; h < 20; h += 1) {
        for (int i = 1; i <= sum[n]; i += 1) {
            anc[h][i] = anc[h - 1][anc[h - 1][i]];
        }
    }
    for (int h = 0; h < 20; h += 1) {
        for (int i = 1; i <= sum[n]; i += 1) {
            f[h][i] = get(i, (1 << h) - 1);
        }
    }
    for (int h = 1; h < 20; h += 1) {
        for (int i = 1; i <= sum[n]; i += 1) {
            int x = f[h - 1][i];
            t[h][i] = join(t[h - 1][i], t[h - 1][anc[h - 1][i]], x, anc[0][x]);
        }
    }

    cin >> q;
    for (int iq = 1; iq <= q; iq += 1) {
        int l, r;
        cin >> l >> r;
        ll ans = 1e18;
        for (int i = sum[l - 1] + 1; i <= sum[l]; i += 1) {
            ans = min(ans, lift(i, r - l));
        }
        cout << ans << "\n";
    }
    return 0;
}

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