제출 #1267074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267074		dima2101	Railway Trip 2 (JOI22_ho_t4)	C++20	35 / 100	229 ms	21008 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));
    }
};


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

    SegTree t(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--;

        t.upd(0,0,n,all[i].first,i,all[i].second);
    }
    for(int i = 0;i < m;i++){
        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;
        }
        // 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]; 
        }
    }
    int q;
    std::cin>>q;
    while(q--){
        int start,stop;
        std::cin>>start>>stop;
        start--;
        stop--;

        int left = 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;
    }
}

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