Submission #831749

#	Time	Username	Problem	Language	Result	Execution time	Memory
831749		jasmin	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	1218 ms	91780 KiB

Main

//JOI 2022 Final Round
#include<bits/stdc++.h>
using namespace std;

const int L=25;
const int INF=1e9+7;

struct segtree{
    vector<pair<int,int> > tree;

    segtree(int n){
        tree.assign(n*4, {INF, -1});
    }

    pair<int,int> merge(pair<int,int> a, pair<int,int> b){
        pair<int,int> ans;
        ans.first = min(a.first, b.first);
        ans.second = max(a.second, b.second);
        return ans;
    }

    pair<int,int> update(int l, int r, int v, int x, pair<int,int> val){
        if(x<l || r<=x) return tree[v];
        if(l+1==r){
            return tree[v]=val;
        }
        int m=l+(r-l)/2;
        return tree[v] = merge(update(l, m, v*2+1, x, val), update(m, r, v*2+2, x, val));
    }

    pair<int,int> query(int l, int r, int v, int ql, int qr){
        if(qr<=l || r<=ql) return {INF, -1};
        if(ql<=l && r<=qr){
            return tree[v];
        }
        int m=l+(r-l)/2;
        return merge(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    int m;
    cin >> m;
    vector<int> val(m);
    vector<pair<int, pair<int, int> > >events;
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;

        if(a < b){

            events.push_back({a, {1, i}});
            events.push_back({min(a+k, b), {2, i}});
            val[i] = b;
        }
        else{
            swap(a, b);

            events.push_back({max(b-k+1, a), {1, i}});
            events.push_back({b+1, {2, i}});
            val[i] = a;

        }
    }
    sort(events.begin(), events.end());

    /*for(auto [a, x]: events){
        auto [b, c] = x;

        cout << a << " " << b << " " << c << "=> " << val[c] << "\n";
    }*/


    vector<segtree> range(L, n+1);

    int ind=0;
    set<pair<int,int> > active;
    for(int i=1; i<=n; i++){

        while(ind < 2*m && events[ind].first<=i){

            auto [x, j] = events[ind].second;
            if(x==1){
                active.insert({val[j], j});
            }
            else{
                active.erase({val[j], j});
            }
            ind++;
        }

        int l =i;
        int r =i;
        if(!active.empty()){

            r = max(i, (*prev(active.end())).first);

            l = min(i, (*active.begin()).first);
        }
       
        range[0].update(0, n+1, 0, i, {l, r});
    }

    for(int k=1; k<L; k++){
        //cout << k << "\n";
        for(int i=1; i<=n; i++){

            auto [l, r] = range[k-1].query(0, n+1, 0, i, i+1);
            auto [l2, r2] = range[k-1].query(0, n+1, 0, l, r+1);


            //cout << i << ": " << l2 << " " << r2 << "\n";

            range[k].update(0, n+1, 0, i, {l2, r2});
        }
    }


    int q;
    cin >> q;
    for(int i=0; i<q; i++){
        int s, t;
        cin >> s >> t;

        auto rangebig = range[L-1].query(0, n+1, 0, s, s+1);
        //cout << rangebig.first << " " << rangebig.second << "\n";
        if(t < rangebig.first || rangebig.second < t){
            cout << -1 << "\n";
            continue;
        }

        if(s==t){
            cout << 0 << "\n";
            continue;
        }

        pair<int,int> r={s, s};
        int ans=0;
        for(int k=L-1; k>=0; k--){

            auto rangenext = range[k].query(0, n+1, 0, r.first, r.second+1);
            if(t < rangenext.first || rangenext.second < t){
                r=rangenext;
                ans += (1<<k);
            }

        }

        cout << ans+1 << "\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