Submission #1127959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127959		antonn	Escape Route 2 (JOI24_escape2)	C++20	54 / 100	3096 ms	108728 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()


const int K = 250;


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;
}


vector<vector<int>> revg;
vector<vector<int>> revanc, revf;
vector<vector<ll>> revt;
vector<int> RA, RB;


void revdfs(int u, int p = 0) {
    revanc[0][u] = p;
    for (auto v : revg[u]) {
        revdfs(v, u);
    }
}


ll revjoin(ll t1, ll t2, int x, int y) { 
    if (RB[y] <= RA[x]) {
        return t1 + RA[x] - RB[y] + t2;
    } else {
        return t1 + T - RB[y] + RA[x] + t2;
    }
}


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


ll revlift(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 = revt[h][a];
            } else {
                ans = revjoin(ans, revt[h][a], b, a);
            }
            b = revf[h][a];
            a = revanc[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]);
        }
    }

    // invers
    auto reva = a;
    for (int i = 1; i <= n; i += 1) {
        sort(all(reva[i]), [&](pair<int, int> a, pair<int, int> b) {
            return a.second <= b.second;
        });
    }
    vector<vector<pair<int, int>>> pref(n + 1);
    for (int i = 1; i <= n; i += 1) {
        pref[i].resize(m[i]);
        pref[i][0] = {reva[i][0].first, 0};
        for (int j = 1; j < m[i]; j += 1) {
            pref[i][j] = max(pref[i][j - 1], {reva[i][j].first, j});
        }
    }
    revg.resize(sum[n] + 1);
    for (int i = 2; i <= n - 1; i += 1) {
        for (int j = 0; j < m[i]; j += 1) {
            int A = reva[i][j].first;
            int B = reva[i][j].second;
            int l = 0, r = m[i - 1] - 1, sol = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (reva[i - 1][mid].second <= A) {
                    sol = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            if (sol == -1) {
                revg[get_id(i - 1, pref[i - 1][m[i - 1] - 1].second)].push_back(get_id(i, j));
                
            } else {
                revg[get_id(i - 1, pref[i - 1][sol].second)].push_back(get_id(i, j));
            }
        }
    }
    revanc.assign(20, vector<int>(sum[n] + 1));
    revf.assign(20, vector<int>(sum[n] + 1));
    revt.assign(20, vector<ll>(sum[n] + 1));
    RA.resize(sum[n] + 1);
    RB.resize(sum[n] + 1);
    for (int i = 1; i <= m[1]; i += 1) {
        revdfs(i);
    }
    for (int i = 1; i <= n; i += 1) {
        for (int j = 0; j < m[i]; j += 1) {
            revt[0][get_id(i, j)] = reva[i][j].second - reva[i][j].first; 
            RA[get_id(i, j)] = reva[i][j].first;
            RB[get_id(i, j)] = reva[i][j].second;
        }
    }
    for (int h = 1; h < 20; h += 1) {
        for (int i = 1; i <= sum[n]; i += 1) {
            revanc[h][i] = revanc[h - 1][revanc[h - 1][i]];
        }
    }
    for (int h = 0; h < 20; h += 1) {
        for (int i = 1; i <= sum[n]; i += 1) {
            revf[h][i] = revget(i, (1 << h) - 1);
        }
    }
    for (int h = 1; h < 20; h += 1) {
        for (int i = 1; i <= sum[n]; i += 1) {
            int x = revf[h - 1][i];
            revt[h][i] = revjoin(revt[h - 1][i], revt[h - 1][revanc[h - 1][i]], x, revanc[0][x]);
        }
    }

    vector<int> heavy;
    for (int i = 1; i <= n; i += 1) {
        if (m[i] >= K) {
            heavy.push_back(i);
        }
    }
    map<pair<int, int>, ll> ans;
    for (int i = 0; i < heavy.size(); i += 1) {
        for (int j = i; j < heavy.size(); j += 1) {
            int x = heavy[i];
            int y = heavy[j] + 1;
            for (int k = sum[x - 1] + 1; k <= sum[x]; k += 1) {
                ll cur = lift(k, y - x);
                if (ans.count({x, y}) == 0) {
                    ans[{x, y}] = cur;
                } else {
                    ans[{x, y}] = min(ans[{x, y}], cur);
                }
            }
        }
    }
    cin >> q;
    for (int iq = 1; iq <= q; iq += 1) {
        int l, r;
        cin >> l >> r;
        if (m[l] >= K && m[r - 1] >= K) {
            cout << ans[{l, r}] << "\n";
            continue;
        }
        ll ans = 1e18;
        if (m[l] <= K) {
            for (int i = sum[l - 1] + 1; i <= sum[l]; i += 1) {
                ans = min(ans, lift(i, r - l));
            }
        } else {
            for (int i = sum[r - 2] + 1; i <= sum[r - 1]; i += 1) {
                ans = min(ans, revlift(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