Submission #946553

#	Time	Username	Problem	Language	Result	Execution time	Memory
946553		vladilius	Railway Trip 2 (JOI22_ho_t4)	C++17	0 / 100	128 ms	26568 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, 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});
    }
    int lg = ceil(log2(n));
    pii sp[n + 1][lg + 1];
    for (int i = 1; i <= n; i++){
        sp[i][0] = {i, i};
    }
    
    auto mr = [&](pii x, pii y) -> pii{
        return {min(x.first, y.first), max(x.second, y.second)};
    };
    
    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 = max(x + 1, y - k + 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));
        }
    }
        
    for (int j = 1; j <= lg; j++){
        for (int i = 1; i + (1 << j) <= n + 1; i++){
            pii T = sp[i][j - 1];
            sp[i][j] = mr(mr(T, sp[T.first][j - 1]), sp[T.second][j - 1]);
        }
    }
    
    auto can = [&](pii x, int p) -> bool{
        return (x.first <= p && p <= x.second);
    };
    auto val = [&](pii x) -> bool{
        return (x.first || x.second);
    };
    int q; cin>>q;
    while (q--){
        int s, t; cin>>s>>t;
        int p = 0;
        while (sp[s][p].first || sp[s][p].second) p++;
        if (!can(sp[s][p - 1], t)){
            cout<<-1<<"\n";
            continue;
        }
        pii cur = {s, s};
        int out = 1;
        for (int i = lg; i >= 0; i--){
            pii m = cur;
            if (val(sp[cur.second][i])){
                m = mr(m, sp[cur.second][i]);
            }
            if (val(sp[cur.first][i])){
                m = mr(m, sp[cur.first][i]);
            }
            if (m == cur) continue;
            if (!can(m, t)){
                out++;
                cur = m;
            }
        }
        cout<<out<<"\n";
    }
}

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