Submission #594090

#	Time	Username	Problem	Language	Result	Execution time	Memory
594090		piOOE	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	366 ms	258188 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

template<typename T>
struct SparseTableMax { //max
    int n;
    vector<vector<T>> st;

    SparseTableMax(const vector<T> &a) {
        init(a);
    }

    void init(const vector<T>& a) {
        n = static_cast<int>(a.size());
        int max_log = 32 - __builtin_clz(n);
        st.resize(max_log);
        st[0] = a;
        for (int j = 1; j < max_log; ++j) {
            st[j].resize(n - (1 << j) + 1);
            for (int i = 0; i <= n - (1 << j); ++i) {
                st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    SparseTableMax() = default;

    T get(int L, int R) const {
        assert(0 <= L && L < R && R <= n);
        int lg = __lg(R - L);
        return max(st[lg][L], st[lg][R - (1 << lg)]);
    }
};

template <typename T>
struct SparseTableMin { //min
    int n;
    vector<vector<T>> st;

    SparseTableMin(const vector<T>& a) {
        init(a);
    }

    void init(const vector<T>& a) {
        n = static_cast<int>(a.size());
        int max_log = 32 - __builtin_clz(n);
        st.resize(max_log);
        st[0] = a;
        for (int j = 1; j < max_log; ++j) {
            st[j].resize(n - (1 << j) + 1);
            for (int i = 0; i <= n - (1 << j); ++i) {
                st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    SparseTableMin() = default;

    T get(int L, int R) const {
        assert(0 <= L && L < R && R <= n);
        int lg = __lg(R - L);
        return min(st[lg][L], st[lg][R - (1 << lg)]);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, m;
    cin >> n >> k >> m;
    vector<vector<int>> qu(n);
    vector<pair<int, int>> b(m);
    for (int i = 0; i < m; ++i) {
        cin >> b[i].first >> b[i].second;
        --b[i].first, --b[i].second;
    }
    //from left to right
    for (int i = 0; i < m; ++i) {
        if (b[i].first < b[i].second) {
            qu[b[i].first].push_back(b[i].second);
            int r = min(b[i].first + k, b[i].second);
            qu[r].push_back(~b[i].second);
        }
    }
    int logn = 20;
    vector<vector<int>> R(logn, vector<int>(n)), L(logn, vector<int>(n));
    multiset<int, greater<>> st1;
    for (int i = 0; i < n; ++i) {
        for (int r : qu[i]) {
            if (r >= 0) {
                st1.insert(r);
            } else {
                st1.extract(~r);
            }
        }
        qu[i].clear();
        if (st1.empty()) {
            R[0][i] = i;
        } else {
            R[0][i] = *st1.begin();
        }
    }
    //from right to left
    for (int i = 0; i < m; ++i) {
        if (b[i].first > b[i].second) {
            qu[b[i].first].push_back(b[i].second);
            int l = max(b[i].second, b[i].first - k);
            qu[l].push_back(~b[i].second);
        }
    }
    multiset<int> st2;
    for (int i = n - 1; i > -1; --i) {
        for (int l : qu[i]) {
            if (l >= 0) {
                st2.insert(l);
            } else {
                st2.extract(~l);
            }
        }
        qu[i].clear();
        if (st2.empty()) {
            L[0][i] = i;
        } else {
            L[0][i] = *st2.begin();
        }
    }
    //calc binups
    SparseTableMax<int> stR[logn];
    SparseTableMin<int> stL[logn];
    for (int j = 1; j < logn; ++j) {
        stR[j - 1].init(R[j - 1]);
        stL[j - 1].init(L[j - 1]);
        for (int i = 0; i < n; ++i) {
            L[j][i] = stL[j - 1].get(L[j - 1][i], R[j - 1][i] + 1);
            R[j][i] = stR[j - 1].get(L[j - 1][i], R[j - 1][i] + 1);
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int s, t;
        cin >> s >> t;
        --s, --t;
        if (s < t) {
            if (R[logn - 1][s] < t) {
                cout << "-1\n";
                continue;
            }
            int ans = 0;
            int l = s, r = s;
            for (int j = logn - 1; j > -1; --j) {
                if (R[j][s] < t) {
                    ans += 1 << j;
                    r = R[j][s];
                    l = L[j][s];
                    break;
                }
            }
            for (int j = logn - 2; j > -1; --j) {
                if (stR[j].get(l, r + 1) < t) {
                    int rr = stR[j].get(l, r + 1);
                    int ll = stL[j].get(l, r + 1);
                    r = rr, l = ll;
                    ans += 1 << j;
                }
            }
            cout << ans + 1 << '\n';
        } else {
            if (L[logn - 1][s] > t) {
                cout << "-1\n";
                continue;
            }
            int ans = 0;
            int l = s, r = s;
            for (int j = logn - 1; j > -1; --j) {
                if (L[j][s] > t) {
                    ans += 1 << j;
                    r = R[j][s];
                    l = L[j][s];
                    break;
                }
            }
            for (int j = logn - 2; j > -1; --j) {
                if (stL[j].get(l, r + 1) > t) {
                    int rr = stR[j].get(l, r + 1);
                    int ll = stL[j].get(l, r + 1);
                    r = rr, l = ll;
                    ans += 1 << j;
                }
            }
            cout << ans + 1 << '\n';
        }
    }
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13