Submission #864217

#	Time	Username	Problem	Language	Result	Execution time	Memory
864217		prairie2022	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	308 ms	257044 KiB

Main

#include<bits/stdc++.h>
typedef long long ll;
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define pii pair<int, int>
#define F first 
#define S second

inline pii operator+(pii p1, pii p2){
    return {min(p1.F, p2.F), max(p1.S, p2.S)};
}

vector<vector<vector<pii>>> table; // __lg(#train), __lg(range), range_left
void build(int n, int k){
    int m, a, b;
    vector<vector<int>> l(n+1), r(n+1);
    for(cin >> m; m; m--){
        cin >> a >> b;
        if(a<b){
            l[a].push_back(b);
            r[min(a+k-1, b-1)].push_back(b);
        }
        else{
            l[max(a-k+1, b+1)].push_back(b);
            r[a].push_back(b);
        }
    }
    multiset<int> s;
    for(int i=1; i<=n; i++){
        for(const int &st: l[i]) s.insert(st);
        if(!s.empty()) table[0][0][i] = {min(i, *s.begin()), max(i, *s.rbegin())};
        else table[0][0][i] = {i, i};
        for(const int &st: r[i]) s.erase(s.find(st));
    }
}

inline pii get(int t, pii p){
    p.S++;
    int tmp = __lg(p.S-p.F);
    return table[t][tmp][p.F]+table[t][tmp][p.S-(1<<tmp)];
}

inline bool out(int t, pii p){
    return p.F>t || t>p.S;
}

int main(){
    fastio
    int n, k, y, q, s, t;
    cin >> n >> k;
    y = __lg(n)+1;
    table.assign(y+1, vector<vector<pii>>(y, vector<pii>(n+1))); 
    build(n, k);
    // sprase table
    for(int t=0; t<=y; t++){
        if(t){
            for(int i=1; i<=n; i++)
                table[t][0][i] = get(t-1, table[t-1][0][i]);
        }
        for(int j=0; j<y-1; j++){
            for(int i=1; i<=n-(1<<j); i++)
                table[t][j+1][i] = table[t][j][i]+table[t][j][i+(1<<j)];
        }
    }
    // query
    for(cin >> q; q; q--){
        cin >> s >> t;
        if(out(t, table[y][0][s])){
            cout << "-1\n";
            continue;
        }
        int ans = 0;
        pii cur = {s, s};
        for(int tt=y-1; tt>-1; tt--){
            pii tmp = get(tt, cur);
            if(out(t, tmp)){
                ans ^= 1<<tt;
                cur = tmp;
            }
        }
        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