Submission #1267767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267767		enzy	Railway Trip 2 (JOI22_ho_t4)	C++20	16 / 100	2099 ms	133416 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int inf=1e9+7;
const int maxk=18;
int esq[maxn][maxk], dir[maxn][maxk];
pair<int,int> seg[4*maxn][2], aux_seg[4*maxn][maxk][2];

void refresh(int id, int ini, int fim, int oq){
    if(ini!=fim){
        int e=2*id, d=2*id+1;
        if(!oq){
            seg[e][oq].second=min(seg[e][oq].second,seg[id][oq].second);
            seg[d][oq].second=min(seg[d][oq].second,seg[id][oq].second);
        }else{
            seg[e][oq].second=max(seg[e][oq].second,seg[id][oq].second);
            seg[d][oq].second=max(seg[d][oq].second,seg[id][oq].second);
        }
    }
    if(!oq){
        seg[id][oq].first=min(seg[id][oq].first,seg[id][oq].second);
        seg[id][oq].second=inf;
    }else{
        seg[id][oq].first=max(seg[id][oq].first,seg[id][oq].second);
        seg[id][oq].second=0;
    }
}


void update(int id, int ini, int fim, int l, int r, int val, int oq){
    refresh(id,ini,fim,oq);
    if(ini>r||fim<l) return;
    if(l<=ini&&fim<=r){
        if(!oq) seg[id][oq].second=min(seg[id][oq].second,val);
        else seg[id][oq].second=max(seg[id][oq].second,val);
        refresh(id,ini,fim,oq);
        return;
    }
    int mid=(ini+fim)/2, e=2*id, d=2*id+1;
    update(e,ini,mid,l,r,val,oq); update(d,mid+1,fim,l,r,val,oq);
    if(!oq) seg[id][oq].first=min(seg[e][oq].first,seg[d][oq].first);
    else seg[id][oq].first=max(seg[e][oq].first,seg[d][oq].first);
}



int query(int id, int ini, int fim, int l, int r, int oq){
    refresh(id,ini,fim,oq);
    if(ini>r||fim<l){
        if(!oq) return inf;
        else return 0;
    }
    if(l<=ini&&fim<=r) return seg[id][oq].first;
    int mid=(ini+fim)/2, e=2*id, d=2*id+1;
    if(!oq) return min(query(e,ini,mid,l,r,oq),query(d,mid+1,fim,l,r,oq));
    return max(query(e,ini,mid,l,r,oq),query(d,mid+1,fim,l,r,oq));
}

void aux_refresh(int id, int ini, int fim, int b, int oq){
    if(ini!=fim){
        int e=2*id, d=2*id+1;
        if(!oq){
            aux_seg[e][b][oq].second=min(aux_seg[e][b][oq].second,aux_seg[id][b][oq].second);
            aux_seg[d][b][oq].second=min(aux_seg[d][b][oq].second,aux_seg[id][b][oq].second);
        }else{
            aux_seg[e][b][oq].second=max(aux_seg[e][b][oq].second,aux_seg[id][b][oq].second);
            aux_seg[d][b][oq].second=max(aux_seg[d][b][oq].second,aux_seg[id][b][oq].second);
        }
    }
    if(!oq){
        aux_seg[id][b][oq].first=min(aux_seg[id][b][oq].first,aux_seg[id][b][oq].second);
        aux_seg[id][b][oq].second=inf;
    }else{
        aux_seg[id][b][oq].first=max(aux_seg[id][b][oq].first,aux_seg[id][b][oq].second);
        aux_seg[id][b][oq].second=0;
    }
}

void aux_update(int id, int ini, int fim, int l, int r, int val, int b, int oq){
    aux_refresh(id,ini,fim,b,oq);
    if(ini>r||fim<l) return;
    if(l<=ini&&fim<=r){
        if(!oq) aux_seg[id][b][oq].second=min(aux_seg[id][b][oq].second,val);
        else aux_seg[id][b][oq].second=max(aux_seg[id][b][oq].second,val);
        aux_refresh(id,ini,fim,b,oq);
        return;
    }
    int mid=(ini+fim)/2, e=2*id, d=2*id+1;
    aux_update(e,ini,mid,l,r,val,b,oq); aux_update(d,mid+1,fim,l,r,val,b,oq);
    if(!oq) aux_seg[id][b][oq].first=min(aux_seg[e][b][oq].first,aux_seg[d][b][oq].first);
    else aux_seg[id][b][oq].first=max(aux_seg[e][b][oq].first,aux_seg[d][b][oq].first);
}



int aux_query(int id, int ini, int fim, int l, int r, int b, int oq){
    aux_refresh(id,ini,fim,b,oq);
    if(ini>r||fim<l){
        if(!oq) return inf;
        else return 0;
    }
    if(l<=ini&&fim<=r) return aux_seg[id][b][oq].first;
    int mid=(ini+fim)/2, e=2*id, d=2*id+1;
    if(!oq) return min(aux_query(e,ini,mid,l,r,b,oq),aux_query(d,mid+1,fim,l,r,b,oq));
    return max(aux_query(e,ini,mid,l,r,b,oq),aux_query(d,mid+1,fim,l,r,b,oq));
}

void solve(int n){
    int s, t; cin >> s >> t;
    int resp=0, l=s, r=s;
    if(esq[s][maxk-1]>t||dir[s][maxk-1]<t) cout << -1 << endl;
    else{
        for(int b=maxk-1;b>=0;b--){
            int nl=aux_query(1,1,n,l,r,b,0), nr=aux_query(1,1,n,l,r,b,1);
            if(nl>t||nr<t){
                l=nl; r=nr;
                resp+=(1<<b);
            }
        }
        cout << resp+1 << endl;
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, k, m; cin >> n >> k >> m;
    for(int i=0;i<=4*n;i++){
        for(int b=0;b<maxk;b++){
            aux_seg[i][b][0].first=aux_seg[i][b][0].second=inf;
            aux_seg[i][b][1].first=aux_seg[i][b][1].second=0;
        }
        seg[i][0].first=seg[i][0].second=inf;
        seg[i][1].first=seg[i][1].second=0;
    }
    for(int i=1;i<=n;i++){
        update(1,1,n,i,i,i,0);
        update(1,1,n,i,i,i,1);
    }
    for(int i=1;i<=m;i++){
        int a, b; cin >> a >> b;
        if(a<b) update(1,1,n,a,min(a+k-1,b),b,1);
        else{
            swap(a,b);
            update(1,1,n,max(b-k+1,a),b,a,0);
        }
    }
    for(int i=1;i<=n;i++){
        esq[i][0]=query(1,1,n,i,i,0);
        dir[i][0]=query(1,1,n,i,i,1);
        aux_update(1,1,n,i,i,esq[i][0],0,0);
        aux_update(1,1,n,i,i,dir[i][0],0,1);
    }
    for(int b=1;b<maxk;b++){
        for(int i=1;i<=n;i++){
            int l=esq[i][b-1], r=dir[i][b-1];
            esq[i][b]=aux_query(1,1,n,l,r,b-1,0);
            dir[i][b]=aux_query(1,1,n,l,r,b-1,1);
            aux_update(1,1,n,i,i,esq[i][b],b,0);
            aux_update(1,1,n,i,i,dir[i][b],b,1);
        }
    }
    int q; cin >> q;
    while(q--) solve(n);
}

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