Submission #810364

#	Time	Username	Problem	Language	Result	Execution time	Memory
810364		vjudge1	Railway Trip 2 (JOI22_ho_t4)	C++17	0 / 100	84 ms	37160 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 10;

template<typename T> 
struct SparseTable {
    vector<vector<T>> st;
    T (*F) (T, T);
    int len;
    void init(vector<T> &a, T(*f)(T, T)) {
        len = (int)a.size();
        int mxpow = 32 - __builtin_clz(len);
        F = f;
        st.resize(mxpow);
        st[0] = a;
        for(int k = 1; k < mxpow; k++) {
            st[k].resize(len - (1 << k) + 1);
            for(int i = 0; i < (int)st[k].size(); i++) 
                st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
        }
    }
    T get(int l, int r) {
        if(l > r || l < 0 || r >= len) {
            cerr << "Wrong range in Sparse Table\n";
            exit(0);
        }
        int k = 31 - __builtin_clz(r - l + 1);
        return F(st[k][l], st[k][r - (1 << k) + 1]);
    }
};

int n, k, m;
int A[N], B[N];
int rb[N], lb[N];
SparseTable<pair<int, int>> st_rb, st_lb;

void calculate() {
    static vector<int> op[N], cl[N];
    for(int i = 0; i < m; i++) {
        if(A[i] < B[i]) {
            op[A[i]].push_back(B[i]);
            cl[min(B[i] + 1, A[i] + k)].push_back(B[i]);
        }
    }
    multiset<int> ms;
    for(int i = 1; i <= n; i++) {
        for(int x : cl[i]) 
            ms.erase(ms.find(x));
        for(int x : op[i]) 
            ms.insert(x);
        rb[i] = (ms.empty() ? i : *(--ms.end()));
    }
    vector<pair<int, int>> t(n + 1);
    for(int i = 1; i <= n; i++) {
        t[i] = {rb[i], i};
    }
    st_rb.init(t, [](pair<int, int> x, pair<int, int> y) {return (x > y ? x : y);});
    
    ms.clear();
    for(int i = 1; i <= n; i++) {
        op[i].clear();
        cl[i].clear();
    }
    for(int i = 0; i < m; i++) {
        if(A[i] > B[i]) {
            op[A[i]].push_back(B[i]);
            cl[max(B[i] - 1, A[i] - k)].push_back(B[i]);
        }
    }
    for(int i = n; i >= 1; i--) {
        for(int x : cl[i]) 
            ms.erase(ms.find(x));
        for(int x : op[i]) 
            ms.insert(x);
        lb[i] = (ms.empty() ? i : *(ms.begin()));
    }
    for(int i = 1; i <= n; i++) {
        t[i] = {lb[i], i};
    }
    st_lb.init(t, [](pair<int, int> x, pair<int, int> y) {return (x < y ? x : y);});

}

int f[N][20];
void build() {
    for(int i = n; i >= 1; i--) {
        f[i][0] = i;
        for(int k = 1; k < 20; k++) {
            int p = st_rb.get(f[i][k - 1], rb[f[i][k - 1]]).second;
            f[i][k] = f[p][k - 1];
        }
        // cout << i << ": ";
        // for(int k = 0; k < 4; k++) 
        //     cout << f[i][k] << ' ';
        // cout << '\n';
        // cout << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> k >> m;
    bool flag = 0;
    for(int i = 0; i < m; i++) {
        cin >> A[i] >> B[i];
        flag |= (A[i] > B[i]);
    }
    if(flag) {
        cout << "WA\n";
        return 0;
    }
    calculate();
    // build();
    // for(int i = 1; i <= n; i++) 
    //     cout << lb[i] << ' ';
    // cout << '\n';
    // for(int i = 1; i <= n; i++) 
    //     cout << rb[i] << ' ';
    // cout << '\n';
    // return 0;
    int q;
    cin >> q;
    while(q--) {
        int s, t, ans = 1;
        cin >> s >> t;
        while(rb[s] < t) {
            ans++;
            int next = st_rb.get(s, rb[s]).second;
            // cout << s << ' ';
            if(next == s) {
                ans = -1;
                break;
            }
            s = next;
        } 
        // cout << '\n';
        cout << ans << '\n';
        // for(int k = 19; k >= 0; k--) {
        //     if(rb[f[s][k]] < t) s = f[f[s][k]][1], ans += (1 << k);
        // }
        // s = f[s][1], ans++;
        // cout << s << ' ' << ans << '\n';
        // if(rb[s] < t) ans = -1;
        // else ans += (s < t);
        // cout << ans << '\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