Submission #1276514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276514		Sofiatpc	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	1940 ms	40160 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+5, B = 17; 
int mn[B+5][MAXN*4], mx[B+5][MAXN*4], lzmn[MAXN*4], lzmx[MAXN*4];

void build(int node, int l, int r){
    lzmn[node] = MAXN;
    if(l == r){
        mn[0][node] = l; mx[0][node] = l;
        return;
    }

    int mid = (l+r)/2 , e =node*2, d = node*2+1;
    build(e,l,mid); build(d,mid+1,r);
    mn[0][node] = min(mn[0][e],mn[0][d]); mx[0][node] = max(mx[0][e],mx[0][d]);
}

void refresh(int node, int l, int r){
    mn[0][node] = min(mn[0][node],lzmn[node]); mx[0][node] = max(mx[0][node],lzmx[node]);

    if(l != r){
        lzmn[node*2] = min(lzmn[node*2], lzmn[node]); lzmn[node*2+1] = min(lzmn[node*2+1], lzmn[node]);
        lzmx[node*2] = max(lzmx[node*2], lzmx[node]); lzmx[node*2+1] = max(lzmx[node*2+1], lzmx[node]);
    }
    lzmn[node] = MAXN; lzmx[node] = 0; 
}

void update(int node, int l, int r, int i, int j, int t, int x){
    refresh(node,l,r);
    if(j < l || r < i)return;
    if(i <= l && r <= j){
        if(t == 0)lzmn[node] = x;
        else lzmx[node] = x;
        refresh(node,l,r);
        return;
    }

    int mid = (l+r)/2 , e = node*2,d = node*2+1;
    update(e,l,mid,i,j,t,x); update(d,mid+1,r,i,j,t,x);
    mx[0][node] = max(mx[0][e],mx[0][d]); mn[0][node] = min(mn[0][e],mn[0][d]);
}

int queryMN(int node, int l, int r, int i, int j, int k){
    if(k == 0)refresh(node,l,r);

    if(j < l || r < i)return MAXN;
    if(i <= l && r <= j)return mn[k][node];
    int mid = (l+r)/2, e = node*2, d = node*2+1;
    return min(queryMN(e,l,mid,i,j,k), queryMN(d,mid+1,r,i,j,k));
}

int queryMX(int node, int l, int r, int i, int j, int k){
    if(k == 0)refresh(node,l,r);

    if(j < l || r < i)return 0;
    if(i <= l && r <= j)return mx[k][node];
    int mid = (l+r)/2, e = node*2, d = node*2+1;
    return max(queryMX(e,l,mid,i,j,k), queryMX(d,mid+1,r,i,j,k));
}

void updateP(int node, int l, int r, int i, int k, int lx, int rx){
    if(r < i || i < l)return;
    if(l == r){
        mn[k][node] = lx; mx[k][node] = rx;
        return;
    }
    int mid = (l+r)/2, e = node*2, d = node*2+1;
    updateP(e,l,mid,i,k,lx,rx); updateP(d,mid+1,r,i,k,lx,rx);
    mx[k][node] = max(mx[k][e],mx[k][d]); mn[k][node] = min(mn[k][e], mn[k][d]);
}

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

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

    build(1,1,n);
    for(int i = 1; i <= m; i++){
        int a,b; cin>>a>>b;
        if(b > a) update(1,1,n, a, min(a+k-1,b), 1, b);
        else update(1,1,n, max(a-k+1,b), a, 0, b);
    }

    for(int k = 1; k <= B; k++){
        for(int i = 1; i <= n; i++){
            int ini = queryMN(1,1,n, i,i, k-1);
            int fim = queryMX(1,1,n, i,i, k-1);
            int l = queryMN(1,1,n, ini, fim, k-1);
            int r = queryMX(1,1,n, ini, fim, k-1);

            updateP(1,1,n, i,k, l,r);
        }
    }

    int q; cin>>q;
    while(q--){
        int s,t; cin>>s>>t;

        int ans = 0, l = s, r = s;
        for(int k = B; k >= 0; k--){
            int ll = queryMN(1,1,n, l, r, k);
            int rr = queryMX(1,1,n, l, r, k);
            if(t < ll || rr < t){l = ll; r = rr; ans += (1<<k);}
        }
        int ll = queryMN(1,1,n, l, r, 0);
        int rr = queryMX(1,1,n, l, r, 0);
        if(t < ll || rr < t)cout<<"-1\n";
        else 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