Submission #1130895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130895		fzyzzz_z	Escape Route 2 (JOI24_escape2)	C++20	100 / 100	1027 ms	139188 KiB

Main

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

using ll = long long;

const int N = 131072; 

multiset<int> t[2 * N]; 

const int inf = 1e9; 

void add(int l, int r, int val, int ind = 1, int L = 0, int R = N - 1) {
    if (l <= L && R <= r) {
        t[ind].insert(val); 
        return; 
    }
    if (r < L || l > R) return; 

    int M = (L + R) / 2; 
    add(l, r, val, 2 * ind, L, M); 
    add(l, r, val, 2 * ind + 1, M + 1, R); 
}
void rem(int l, int r, int val, int ind = 1, int L = 0, int R = N - 1) {
    if (l <= L && R <= r) {
        t[ind].erase(t[ind].find(val)); 
        return; 
    }
    if (r < L || l > R) return; 

    int M = (L + R) / 2; 
    rem(l, r, val, 2 * ind, L, M); 
    rem(l, r, val, 2 * ind + 1, M + 1, R); 
}
int getmin(int x, int ind = 1, int L = 0, int R = N - 1) {
    if (x < L || x > R) return inf; 

    int res = (t[ind].size() ? *t[ind].begin() : inf); 
    if (L == R) return res; 

    int M = (L + R) / 2; 
    res = min(res, getmin(x, 2 * ind, L, M)); 
    res = min(res, getmin(x, 2 * ind + 1, M + 1, R)); 
    return res; 
}


int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); 
    
    int n; 
    ll t; 
    cin >> n >> t; 

    int mm = 0; 

    vector<vector<pair<int, int>>> a(n); 
    vector<vector<int>> xs(n); 
    for (int i = 0; i < n - 1; ++i) {
        int m; 
        cin >> m; 
        mm = max(mm, m); 
        a[i].resize(m); 
        for (auto & [x, y]: a[i]) {
            cin >> x >> y; 
        }
        sort(a[i].begin(), a[i].end()); 

        vector<pair<int, int>> b; 
        for (auto [x, y]: a[i]) {
            if (b.size() && b.back().first == x) continue; 
            while (b.size() && b.back().second >= y) b.pop_back(); 
            b.emplace_back(x, y); 
        }
        a[i] = b; 
        for (auto [x, y]: a[i]) {
            xs[i].push_back(x); 
            xs[i + 1].push_back(y); 
        }
    }
    vector<map<int, int>> id(n);
    map<int, pair<int, int>> to; 
    vector<int> day;  
    int ci = 0; 
    for (int i = 0; i < n; ++i) {
        sort(xs[i].begin(), xs[i].end()); 
        xs[i].erase(unique(xs[i].begin(), xs[i].end()), xs[i].end()); 
        for (auto x: xs[i]) {
            day.push_back(i); 
            id[i][x] = ci++; 

            to[ci - 1] = {i, x}; 
        }
    }
    vector<set<int>> ex(n); 
    for (int i = 0; i < n - 1; ++i) {
        for (auto [x, y]: a[i]) {
            ex[i].insert(x); 
        }
    }
    day.push_back(n); 
    ci++; 
    to[ci - 1] = {n, -1}; 

    vector<vector<pair<int, ll>>> g(ci); 
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < a[i].size(); ++j) {
            int tx = a[i][j].first, ty = a[i][j].second; 
            int x = id[i][tx], y = id[i + 1][ty]; 
            g[y].push_back({x, ty - tx});

            if (i == n - 2) {
                g[ci - 1].push_back({y, 0}); 
            } else {
                auto it = ex[i + 1].lower_bound(ty); 
                if (it == ex[i + 1].end()) {
                    int nt = *(ex[i + 1].begin()); 
                    int tt = nt + t - ty; 
                    g[id[i + 1][nt]].push_back({y, tt}); 
                } else if ((*it) != ty) {
                    g[id[i + 1][*it]].push_back({y, (*it) - ty}); 
                }
            }
        }
    }


    const ll inf = 1e18; 

    vector<ll> dt(ci, inf); // distance to last node that is different 
    vector<int> par(ci, -1); 
    function<void(int)> dfs = [&] (int x) {
        for (auto [y, w]: g[x]) {
            assert(day[y] == day[x] || day[y] == day[x] - 1); 
            par[y] = x; 
            dfs(y); 
            if (day[y] != day[x]) {
                if (w < dt[x]) {
                    dt[x] = w; 
                }
            } else {
                if (w + dt[y] < dt[x]) {
                    dt[x] = w + dt[y]; 
                }
            }
        }
        sort(g[x].begin(), g[x].end(), [&](const pair<int, ll> & y, const pair<int, ll> & z) {
            ll vy = day[y.first] != day[x] ? y.second : y.second + dt[y.first]; 
            ll vz = day[z.first] != day[x] ? z.second : z.second + dt[z.first]; 

            return vy < vz; 
        }); 
    }; 
    dfs(ci - 1); 

    int q; 
    cin >> q; 
    vector<vector<pair<int, int>>> qu(n + 1); 
    map<pair<int, int>, int> has; 

    vector<ll> ans(q, inf); 
    for (int i = 0; i < q; ++i) {
        int x, y; 
        cin >> x >> y; 
        x--; y--; 
        if (has.find({x, y}) != has.end()) {
            ans[i] = -1 - has[{x, y}];
        } else {
            has[{x, y}] = i; 
            qu[x].push_back({y, i}); 
        }
    }

    for (auto & v: qu) {
        sort(v.begin(), v.end()); 
    }
    vector<int> vis(n + 1, 0); 


    vector<ll> path;
    function<int(int)> dfs2 = [&] (int x) {

        assert(n - day[x] == path.size() - 1); 

        if (x != ci - 1 && day[par[x]] != day[x]) {
            int bad = getmin(day[x]); 

            for (auto [i, qi]: qu[day[x]]) {
                if (i > bad) break; 

                ll dist = path.back(); 
                dist -= path[n - i]; 

                ans[qi] = min(ans[qi], dist); 
            }
        }

        int mx = day[x]; 
        int dep1 = -1; 

        for (auto [y, w]: g[x]) {

            if (day[y] == day[x]) path.back() += w; 
            else path.push_back(path.back() + w); 

            int dep = dfs2(y);
            if (y == g[x][0].first) {
                dep1 = dep; 
                add(dep, day[x], day[x]); 
            }

            mx = min(mx, dep); 

            if (day[y] == day[x]) path.back() -= w; 
            else path.pop_back(); 
        }
        if (dep1 != -1) {
            rem(dep1, day[x], day[x]); 
        }

        return mx; 
    }; 

    path.push_back(0LL); 

    dfs2(ci - 1); 

    // for (int i = 0; i < 100; ++i) {
    //     cout << ans[i] << '\n'; 
    // }
    for (auto & x: ans) {
        if (x < 0) x = ans[-(x + 1)];
        cout << x << "\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