Submission #1267116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267116		dima2101	Railway Trip 2 (JOI22_ho_t4)	C++20	87 / 100	1107 ms	39704 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

const int LOGN = 20;
const int MAXN = 2e5 + 1;
int up_max[MAXN][LOGN];
int up_min[MAXN][LOGN];


struct SegTree{
    int n;
    std::vector<std::pair<int,int>> t;
    SegTree(int n):n(n){
        t.resize(4 * n,{-1,-1});
    }

    void upd(int i,int l,int r,int pos,int pos1,int x){
        if(l == r - 1){
            if(x > t[i].first){
                t[i].first = x;
                t[i].second = pos1;
            }
            return;
        }
        int mid = (l + r) / 2;
        if(pos >= mid){
            upd(2 * i + 2,mid,r,pos,pos1,x);
        }else{
            upd(2 * i + 1,l,mid,pos,pos1,x);
        }
        t[i] = std::max(t[2 * i + 1],t[2 * i + 2]);
    }

    std::pair<int,int> query(int i,int l,int r,int ql,int qr){
        if(l>=ql && r <= qr){
            return t[i];
        }
        if(l >= qr || ql >=r){
            return {-1,-1};
        }
        int mid = (l + r) / 2;
        return std::max(query(2 * i + 1,l,mid,ql,qr),
        query(2 *i + 2,mid,r,ql,qr));
    }
};

struct SegTree1{
    int n;
    std::vector<std::pair<int,int>> t;
    SegTree1(int n):n(n){
        t.resize(4 * n,{1e8,1e8});
    }

    void upd(int i,int l,int r,int pos,int pos1,int x){
        if(l == r - 1){
            if(x < t[i].first){
                t[i].first = x;
                t[i].second = pos1;
            }
            return;
        }
        int mid = (l + r) / 2;
        if(pos >= mid){
            upd(2 * i + 2,mid,r,pos,pos1,x);
        }else{
            upd(2 * i + 1,l,mid,pos,pos1,x);
        }
        t[i] = std::min(t[2 * i + 1],t[2 * i + 2]);
    }

    std::pair<int,int> query(int i,int l,int r,int ql,int qr){
        if(l>=ql && r <= qr){
            return t[i];
        }
        if(l >= qr || ql >=r){
            return {1e8,1e8};
        }
        int mid = (l + r) / 2;
        return std::min(query(2 * i + 1,l,mid,ql,qr),
        query(2 *i + 2,mid,r,ql,qr));
    }
};

signed main(){
    int n,k,m;
    std::cin>>n>>k>>m;

    SegTree t(n);
    SegTree1 t1(n);
    std::vector<std::pair<int,int>> all(m);
    for(int i =0 ;i < m;i++){
        std::cin>>all[i].first>>all[i].second;
        all[i].first--;
        all[i].second--;
        if(all[i].first < all[i].second){
            t.upd(0,0,n,all[i].first,i,all[i].second);
        }else{
            
            t1.upd(0,0,n,all[i].first,i,all[i].second);
        }
    }
    int q;
    std::cin>>q;
    if(q * std::max(n,m) <= 1e7){
        for(int i =0 ;i < m;i++){
            if(all[i].first > all[i].second)std::swap(all[i].first,all[i].second);
        }
        for(int i = 0;i < q;i++){
            int start,stop;
            std::cin>>start>>stop;
            start--;
            stop--;

            std::vector<int> dist(n,1e8);
            dist[start] = 0;
            std::queue<int> q;
            q.push(start);
            std::set<int> not_used;
            for(int i =0 ;i < n;i++){
                not_used.insert(i);
            }
            not_used.erase(start);
            while(q.size() > 0){
                int v = q.front();
                // std::cout<<v<<std::endl;
                q.pop();

                int left = std::max(0,v - k + 1);
                int right = v;
                auto r = t.query(0,0,n,left,right + 1);
                if(r.second != -1){
                    // std::cout<<"right"<<' '<<std::max(all[r.second].first,v)<<' '<<all[r.second].second<<std::endl;
                    auto it = not_used.lower_bound(std::max(all[r.second].first,v));
                    std::vector<int> need_del;
                    while(it != not_used.end() && *it <= all[r.second].second){
                        if(dist[*it] > dist[v] + 1){
                            dist[*it] = dist[v] + 1;
                            q.push(*it);
                        }
                        need_del.push_back(*it);
                        it++;
                    }
                    for(int i:need_del){
                        not_used.erase(i);
                    }
                }


                left = v;
                right = std::min(n - 1,v + k - 1);
                // std::cout<<left<<' '<<right<<std::endl;
                auto l = t1.query(0,0,n,left,right + 1);

                if(l.second != 1e8){
                    // std::cout<<"left "<<all[l.second].first<<' '<<all[l.second].second<<std::endl;
                    auto it = not_used.lower_bound(all[l.second].first);
                    std::vector<int> need_del;
                    while(it != not_used.end() && *it <= std::min(v,all[l.second].second)){
                        if(dist[*it] > dist[v] + 1){
                            dist[*it] = dist[v] + 1;
                            q.push(*it);
                        }
                        need_del.push_back(*it);
                        it++;
                    }
                    for(int i:need_del){
                        not_used.erase(i);
                    }
                }
            }

            if(dist[stop] == 1e8){
                std::cout<<-1<<std::endl;
                continue;
            }
            std::cout<<dist[stop]<<std::endl;
        }
        return 0;
    }
    for(int i = 0;i < m;i++){
        if(all[i].first < all[i].second){
            auto now = t.query(0,0,n,all[i].first,all[i].second  +1);
            if(now.first > all[i].second){
                up_max[i][0] = now.second;
            }else{
                up_max[i][0] = i;
            }
        }else{
            std::swap(all[i].second,all[i].first);
            auto now = t1.query(0,0,n,all[i].first,all[i].second + 1);
            if(now.first < all[i].first){
                up_min[i][0] = now.second;
            }else{
                up_min[i][0] = i;
            }
        }
        // std::cout<<i<<' '<<now.second<<std::endl;
    }
    for(int j =1;j < LOGN;j++){
        for(int i = 0;i < m;i++){
            up_max[i][j] = up_max[up_max[i][j - 1]][j - 1]; 
            up_min[i][j] = up_min[up_min[i][j - 1]][j - 1];
        }
    }
   
    while(q--){
        int start,stop;
        std::cin>>start>>stop;
        start--;
        stop--;


        if(start < stop){

            int left = std::max(0,start - k + 1);
            int right = start;
            auto now = t.query(0,0,n,left,right + 1);
            int tmp = now.second;
            if(now.second == -1){
                std::cout<<-1<<std::endl;
                continue;
            }
            if(stop <= now.first){
                std::cout<<1<<std::endl;
                continue;
            }
            // std::cout<<left<<' '<<right<<"dwhsf; "<<now.second<<std::endl;

            int ans = 1;
            for(int j = LOGN - 1;j>=0;j--){
                // std::cout<<up_max[tmp][j]<<std::endl;
                if(all[up_max[tmp][j]].second < stop){
                    ans += (1<<j);
                    tmp = up_max[tmp][j];
                }
            }
            
            if(all[up_max[tmp][0]].second < stop){
                std::cout<<-1<<std::endl;
                continue;
            }
            std::cout<<ans + 1<<std::endl;
        }else{
            int left = start;
            int right = std::min(n - 1,start + k - 1);
            auto now = t1.query(0,0,n,left,right + 1);
            int tmp = now.second;
            // std::cout<<now.second<<' '<<now.first<<' '<<stop<<std::endl;
            if(now.second >= m){
                std::cout<<-1<<std::endl;
                continue;
            }
            if(stop >= now.first){
                std::cout<<1<<std::endl;
                continue;
            }
            // std::cout<<left<<' '<<right<<"dwhsf; "<<now.second<<std::endl;
            assert(tmp < m);
            int ans = 1;
            for(int j = LOGN - 1;j>=0;j--){
                // std::cout<<up_max[tmp][j]<<std::endl;
                if(all[up_min[tmp][j]].first > stop){
                    ans += (1<<j);
                    tmp = up_min[tmp][j];
                }
            }
            
            if(all[up_min[tmp][0]].first > stop){
                std::cout<<-1<<std::endl;
                continue;
            }
            std::cout<<ans + 1<<std::endl;
        }
    }
}

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