Submission #1092895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092895		Trisanu_Das	Railway Trip 2 (JOI22_ho_t4)	C++17	27 / 100	2072 ms	21672 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
    int n, k; cin >> n >> k;
    int l[n + 5], r[n + 5];
    iota(l + 1, l + n + 1, 1);
    iota(r + 1, r + n + 1, 1);
    int m; cin >> m;
    vector<int> add[n + 5], del[n + 5];
    int a[m + 5], b[m + 5];
    for(int i = 1; i <= m; i++){
        cin >> a[i] >> b[i];
        if(a[i] < b[i]){
            add[a[i]].push_back(b[i]);
            del[min(a[i] + k - 1, b[i] - 1)].push_back(b[i]);
        }
    }
    multiset<int, greater<int> > st;
    for(int i = 1; i <= n; i++){
        for(int j : add[i]) st.insert(j);
        if(!st.empty()) r[i] = *st.begin();
        for(int j:del[i]) st.erase(st.find(j));
        add[i].clear();
        del[i].clear();
    }
    for(int i = 1; i <= m; i++){
        if(a[i] > b[i]){
            add[a[i]].push_back(b[i]);
            del[max(a[i] - k + 1, b[i] + 1)].push_back(b[i]);
        }
    }
    st.clear();
    multiset<int> st2;
    for(int i = n; i >= 1; i--){
        for(int j : add[i]) st2.insert(j);
        if(!st2.empty()) l[i]=*st2.begin();
        for(int j:del[i]) st2.erase(st2.find(j));
    }
    int q; cin >> q;
    while(q--){
        int s, t; cin >> s >> t;
        int ans = -1, cur = 0, L = s, R = s;
        vector<int>v;
        v.push_back(s);
        while(!v.empty()){
            int Li = L, Ri = R;
            for(int i : v){
                Li = min(Li, l[i]);
                Ri = max(Ri, r[i]);
                if(i == t){
                    ans = cur;
                    break;
                }
            }
            if(ans > -1) break;
            v.clear();
            for(int i = Li; i < L; i++) v.push_back(i);
            for(int i = Ri; i > R; i--) v.push_back(i);
            L = Li;
            R = Ri;
            cur++;
        }
        cout << ans << '\n';
    }
}

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