Submission #1241795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241795		damoon	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	415 ms	484644 KiB

Main

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("O3,unroll-loops") //main
//#pragma GCC target("avx2") //cf...
//#pragma GCC target("sse4") //Quera

#define ll long long
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;
#define f first
#define s second

#define lc 2*id
#define rc 2*id+1
#define all(x) x.begin(),x.end()

#define pb push_back
#define pp pop_back
#define unicorn(x) x.resize(unique(x.begin(),x.end())-x.begin())

string pr(int* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr( ll* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr(vector<int> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr( vector<ll> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr(pii* vv,int l,int r){for(int i=l;i<r;i++)cout<<"( "<<vv[i].f<<","<<vv[i].s<<" )    ";return "";}
string pr(vector<pii> vv){for(auto i:vv)cout<<"( "<<i.f<<","<<i.s<<" )    ";return "";}

const int L = 1e5+10,lg = 18;
const int inf = 1e9+10;
int n,m,k,q;
int hb[L];
int mx[lg][L],mn[lg][L];

struct stmx{
    int st[lg][L],fn[lg][L];
    stmx(){
        fill(st[0]+1,st[0]+L,0);
        fill(fn[0]+1,fn[0]+L,0);
    }

    void put(int ind,int x){
        st[0][ind] = fn[0][ind] = max(st[0][ind],x);
    }

    void build(){
        for(int j=1;j<lg;j++){
            for(int i=1;i<=n;i++){
                if(i+(1<<j)-1 <= n)
                    st[j][i] = max(st[j-1][i], st[j-1][i+(1<<(j-1))]);
                if(i-(1<<j)+1 >= 1)
                    fn[j][i] = max(fn[j-1][i], fn[j-1][i-(1<<(j-1))]);
            }
        }
    }

    int get(int l,int r){
        if(l > r)
            return 0;
        return max(st[hb[r-l+1]][l],fn[hb[r-l+1]][r]);
    }
};
struct stmn{
    int st[lg][L],fn[lg][L];
    stmn(){
        fill(st[0]+1,st[0]+L,L);
        fill(fn[0]+1,fn[0]+L,L);
    }

    void put(int ind,int x){
        st[0][ind] = fn[0][ind] = min(st[0][ind],x);
    }

    void build(){
        for(int j=1;j<lg;j++){
            for(int i=1;i<=n;i++){
                if(i+(1<<j)-1 <= n)
                    st[j][i] = min(st[j-1][i], st[j-1][i+(1<<(j-1))]);
                if(i-(1<<j)+1 >= 1)
                    fn[j][i] = min(fn[j-1][i], fn[j-1][i-(1<<(j-1))]);
            }
        }
    }

    int get(int l,int r){
        if(l > r)
            return L;
        return min(st[hb[r-l+1]][l],fn[hb[r-l+1]][r]);
    }
};

stmx frf,sx[lg];
stmn frb,sn[lg];

int main(){
    //ofstream cout ("out.out");
    //ifstream cin ("in.in");

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    hb[0] = -1;
    for(int i=1;i<L;i++){
        hb[i] = hb[i/2]+1;
    }

    cin>>n>>k>>m;
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        frf.put(l,r);
        frb.put(l,r);
    }


    frf.build();
    frb.build();
    for(int i=1;i<=n;i++){
        mx[0][i] = max(i,frf.get(max(1,i-k+1),i));
        mn[0][i] = min(i,frb.get(i,min(i+k-1,n)));
        sx[0].put(i,mx[0][i]);
        sn[0].put(i,mn[0][i]);
    }


    sx[0].build();
    sn[0].build();
    for(int x=1;x<lg;x++){
        for(int i=1;i<=n;i++){
            mx[x][i] = sx[x-1].get(mn[x-1][i],mx[x-1][i]);
            mn[x][i] = sn[x-1].get(mn[x-1][i],mx[x-1][i]);
            sx[x].put(i,mx[x][i]);
            sn[x].put(i,mn[x][i]);
        }
        sx[x].build();
        sn[x].build();
    }

    /*
    for(int i=1;i<=n;i++){
        for(int j=0;j<2;j++){
            cout<<"mx["<<j<<"]["<<i<<"]: "<<mn[j][i]<<" "<<mx[j][i]<<endl;
        }
    }
    */

    cin>>q;
    for(int tt=0;tt<q;tt++){
        int S,F;
        cin>>S>>F;
        if(F < mn[lg-1][S] or F > mx[lg-1][S]){
            cout<<-1<<endl;
            continue;
        }
        int l=S, r=S;
        int ans = 0;
        for(int i=lg-1;i>=0;i--){
            pii pre = pii(l,r);
            l = sn[i].get(pre.f,pre.s);
            r = sx[i].get(pre.f,pre.s);
            if(F >= l and F <= r){
                l = pre.f;
                r = pre.s;
            }
            else{
                ans += (1<<i);
            }
        }
        cout<<ans+1<<endl;
    }
}

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