Submission #946647

#	Time	Username	Problem	Language	Result	Execution time	Memory
946647		vladilius	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	550 ms	350184 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int msz = 1e5 + 5;
const int lg = 20;

pii sp[msz][lg];
vector<int> L;
int n;

pii mr(pii x, pii y){
    return {min(x.first, y.first), max(x.second, y.second)};
}

struct SP{
    pii st[msz][lg];
    void build(int j){
        for (int i = 1; i <= n; i++){
            st[i][0] = sp[i][j];
        }
        for (int k = 1; k < lg; k++){
            for (int i = 1; i + (1 << k) <= n + 1; i++){
                st[i][k] = mr(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
            }
        }
    }
    pii get(int l, int r){
        int K = L[r - l + 1];
        return mr(st[l][K], st[r - (1 << K) + 1][K]);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int m, k; cin>>n>>k>>m;
    vector<pii> s1, s2;
    while (m--){
        int a, b; cin>>a>>b;
        if (a > b) s1.push_back({b, a});
        else s2.push_back({a, b});
    }
    for (int i = 1; i <= n; i++){
        sp[i][0] = {i, i};
    }
    
    L.resize(n + 1);
    for (int i = 2; i <= n; i++){
        L[i] = L[i / 2] + 1;
    }
    
    vector<int> in[n + 1], out[n + 1];
    for (auto [x, y]: s1){
        int l = max(x + 1, y - k + 1);
        in[l].push_back(x);
        out[y].push_back(x);
    }
    multiset<int> st;
    for (int i = 1; i <= n; i++){
        for (int j: in[i]){
            st.insert(j);
        }
        if (!st.empty()){
            sp[i][0].first = *st.begin();
        }
        for (int j: out[i]){
            st.erase(st.find(j));
        }
    }
    
    for (int i = 1; i <= n; i++){
        in[i].clear();
        out[i].clear();
    }
    for (auto [x, y]: s2){
        int l = min(x + k - 1, y - 1);
        in[x].push_back(y);
        out[l].push_back(y);
    }
    for (int i = 1; i <= n; i++){
        for (int j: in[i]){
            st.insert(j);
        }
        if (!st.empty()){
            sp[i][0].second = *prev(st.end());
        }
        for (int j: out[i]){
            st.erase(st.find(j));
        }
    }
    
    SP T[lg];
    T[0].build(0);
    for (int j = 1; j < lg; j++){
        for (int i = 1; i <= n; i++){
            pii Y = sp[i][j - 1];
            sp[i][j] = T[j - 1].get(Y.first, Y.second);
        }
        T[j].build(j);
    }
    
    auto can = [&](pii x, int p) -> bool{
        return (x.first <= p && p <= x.second);
    };
    
    int q; cin>>q;
    while (q--){
        int s, t; cin>>s>>t;
        if (!can(sp[s][lg - 1], t)){
            cout<<-1<<"\n";
            continue;
        }
        pii cur = {s, s};
        int out = 1;
        for (int i = lg - 1; i >= 0; i--){
            pii m = T[i].get(cur.first, cur.second);
            if (!can(m, t)){
                cur = m;
                out += (1 << i);
            }
        }
        cout<<out<<"\n";
    }
}

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