제출 #1329047

#제출 시각아이디문제언어결과실행 시간메모리
1329047pvproEscape Route 2 (JOI24_escape2)C++20
100 / 100
1416 ms90256 KiB
#ifndef LOCAL
#pragma GCC Optimize("O3,Ofast,unroll-loops")
#pragma GCC Target("bmi,bmi2,avx,avx2")
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define int ll
#define f first 
#define s second 
#define mp make_pair 
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#ifndef LOCAL
#define endl "\n"
#endif
#define TT template <typename T>
mt19937 rnd(11);
TT
istream& operator>>(istream &in,vector<T>&v){for(auto &x:v)in>>x;return in;}
TT
ostream& operator<<(ostream &out,vector<T>&v){for(auto &x:v)out<<x<<' ';return out;}
TT
istream& operator>>(istream &in,pair<T,T>&p){in>>p.f>>p.s;return in;}

const int LOG_N = 17;

void solve() {
    int n, t;
    cin >> n >> t;
    vector<vector<array<int, 3>>> e(n), re(n);
    vector<array<int, 3>> indexes;
    int ind = 0;
    for (int i = 0; i < n - 1; ++i) {
        int m;
        cin >> m;
        e[i].resize(m);
        int num = 0;
        for (auto &x : e[i]) {
            cin >> x[0] >> x[1];
            indexes.pb({i, x[0], x[1]});
            x[2] = ind++;
        }
    }
    for (int i = 0; i < n; ++i) {
        sort(all(e[i]));
        vector<array<int, 3>> clean;
        for (auto &x : e[i]) {
            while (!clean.empty() && clean.back()[1] >= x[1]) {
                clean.pop_back();
            }
            clean.pb(x);
        }
        e[i] = clean;
        if (e[i].empty()) {
            continue;
        }
        re[i + 1] = e[i];
        for (auto &x : re[i + 1]) {
            swap(x[0], x[1]);
            x[0] = -x[0];
            x[1] = -x[1];
        }
        sort(all(re[i + 1]));
    }
    vector<vector<pii>> binup(LOG_N, vector<pii>(ind)), rbinup(LOG_N, vector<pii>(ind));
    for (int i = 0; i < ind; ++i) {
        if (indexes[i][0] == n - 2) {
            binup[0][i] = mp(i, 0);
        } else {
            auto it = lower_bound(all(e[indexes[i][0] + 1]), array<int, 3>{indexes[i][2], 0ll, 0ll});
            int delta = 0;
            if (it == e[indexes[i][0] + 1].end()) {
                it = e[indexes[i][0] + 1].begin();
                delta = t;
            }
            binup[0][i] = mp((*it)[2], delta);
        }
        if (indexes[i][0] == 0) {
            rbinup[0][i] = mp(i, 0);
        } else {
            auto it = lower_bound(all(re[indexes[i][0]]), array<int, 3>{-indexes[i][1], (int)-1e9, (int)-1e9});
            int delta = 0;
            if (it == re[indexes[i][0]].end()) {
                it = re[indexes[i][0]].begin();
                delta = t;
            }
            rbinup[0][i] = mp((*it)[2], delta);
        }
    }
    for (int l = 1; l < LOG_N; ++l) {
        for (int i = 0; i < ind; ++i) {
            binup[l][i] = mp(binup[l - 1][binup[l - 1][i].f].f, binup[l - 1][binup[l - 1][i].f].s + binup[l - 1][i].s);
            rbinup[l][i] = mp(rbinup[l - 1][rbinup[l - 1][i].f].f, rbinup[l - 1][rbinup[l - 1][i].f].s + rbinup[l - 1][i].s);
        }
    }
    map<pii, int> ans;
    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        if (ans.count(mp(a, b)) == 0) {
            int answer = 1e18;
            int len = b - a - 1;
            if (e[a].size() < re[b].size()) {
                for (auto &x : e[a]) {
                    int v = x[2];
                    int now = 0;
                    for (int l = 0; l < LOG_N; ++l) {
                        if (len&(1<<l)) {
                            now += binup[l][v].s;
                            v = binup[l][v].f;
                        }
                    }
                    answer = min(answer, now + indexes[v][2] - x[0]);
                }
            } else {
                for (auto &x : re[b]) {
                    int v = x[2];
                    int now = 0;
                    for (int l = 0; l < LOG_N; ++l) {
                        if (len&(1<<l)) {
                            now += rbinup[l][v].s;
                            v = rbinup[l][v].f;
                        }
                    }
                    // cout << now << ' ' << indexes[v][1] << ' ' << x[1] << endl;
                    answer = min(answer, now - indexes[v][1] - x[0]);
                }
            }
            ans[mp(a, b)] = answer;
        }
        cout << ans[mp(a, b)] << endl;
    }
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #else
        ios::sync_with_stdio(false);
        cin.tie(0);
    #endif
    int t = 1;
    // cin >> t;
    while (t--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...