제출 #1098385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098385		coldbr3w	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	1170 ms	85920 KiB

Main

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

#define ll int
#define pll pair<int, int>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 2e5 + 100;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n,k,m,q;
pll up[N][19];
struct segment_tree_max_lazy{
    ll n;
    vector<ll>st, lz;
    void init(ll _n){
        n = _n;
        st.clear(); st.resize(4 * n + 10, 0);
        lz.clear(); lz.resize(4 * n + 10, 0);
    }
    void down(ll id, ll l, ll r){
        st[id] = max(lz[id], st[id]);
        if(l != r) lz[2 * id] = max(lz[2 * id], lz[id]), lz[2 * id + 1] = max(lz[2 * id + 1], lz[id]);
        lz[id] = 0;
    }
    void update(ll id, ll l, ll r, ll left, ll right, ll val){
        down(id, l, r);
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            lz[id] = max(lz[id], val);
            down(id, l, r);
            return;
        }
        ll mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, val);
        update(2 * id + 1, mid + 1, r, left, right, val);
        st[id] = max(st[2 * id], st[2 * id + 1]);
    }
    ll get(ll id, ll l, ll r, ll left, ll right){
        down(id, l, r);
        if(l > right || r < left) return 0;
        if(left <= l && r <= right) return st[id];
        ll mid = (l + r) / 2;
        return max(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
    }
    void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
    ll get(ll l, ll r){return get(1,1,n,l,r);}
} st_max;
struct segment_tree_max{
    ll n;
    vector<ll>st;
    void init(ll _n){
        n = _n;
        st.clear(); st.resize(4 * n + 10, 0);
    }
    void update(ll id, ll l, ll r, ll left, ll right, ll val){
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            st[id] = max(st[id], val);
            return;
        }
        ll mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, val);
        update(2 * id + 1, mid + 1, r, left, right, val);
        st[id] = max(st[2 * id], st[2 * id + 1]);
    }
    ll get(ll id, ll l, ll r, ll left, ll right){
        if(l > right || r < left) return 0;
        if(left <= l && r <= right) return st[id];
        ll mid = (l + r) / 2;
        return max(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
    }
    void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
    ll get(ll l, ll r){return get(1,1,n,l,r);}
} R[20];
struct segment_tree_min_lazy{
    ll n;
    vector<ll>st, lz;
    void init(ll _n){
        n = _n;
        st.clear(); st.resize(4 * n + 10, inf);
        lz.clear(); lz.resize(4 * n + 10, inf);
    }
    void down(ll id, ll l, ll r){
        st[id] = min(lz[id], st[id]);
        if(l != r) lz[2 * id] = min(lz[2 * id], lz[id]), lz[2 * id + 1] = min(lz[2 * id + 1], lz[id]);
        lz[id] = inf;
    }
    void update(ll id, ll l, ll r, ll left, ll right, ll val){
        down(id, l, r);
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            lz[id] = min(lz[id], val);
            down(id, l, r);
            return;
        }
        ll mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, val);
        update(2 * id + 1, mid + 1, r, left, right, val);
        st[id] = min(st[2 * id], st[2 * id + 1]);
    }
    ll get(ll id, ll l, ll r, ll left, ll right){
        down(id, l, r);
        if(l > right || r < left) return inf;
        if(left <= l && r <= right) return st[id];
        ll mid = (l + r) / 2;
        return min(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
    }
    void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
    ll get(ll l, ll r){return get(1,1,n,l,r);}
} st_min;
struct segment_tree_min{
    ll n;
    vector<ll>st;
    void init(ll _n){
        n = _n;
        st.clear(); st.resize(4 * n + 10, inf);
    }
    void update(ll id, ll l, ll r, ll left, ll right, ll val){
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            st[id] = min(st[id], val);
            return;
        }
        ll mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, val);
        update(2 * id + 1, mid + 1, r, left, right, val);
        st[id] = min(st[2 * id], st[2 * id + 1]);
    }
    ll get(ll id, ll l, ll r, ll left, ll right){
        if(l > right || r < left) return inf;
        if(left <= l && r <= right) return st[id];
        ll mid = (l + r) / 2;
        return min(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
    }
    void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
    ll get(ll l, ll r){return get(1,1,n,l,r);}
} L[20];
void build(){
    for(int i = 0; i <= 18;i++) L[i].init(n), R[i].init(n);
    for(ll i = 1; i <= n;i++){
        up[i][0] = {min(i, st_min.get(i, i)), max(i, st_max.get(i, i))};
        L[0].update(i, i, up[i][0].F); R[0].update(i, i, up[i][0].S);
    }
    for(int j = 1; j <= 17;j++){
        for(int i = 1; i <= n;i++){
            ll l = up[i][j-1].F, r = up[i][j-1].S;
            up[i][j].F = min(l, L[j-1].get(l, r));
            up[i][j].S = max(r, R[j-1].get(l, r));
        }
        for(int i = 1; i <= n;i++) L[j].update(i, i, up[i][j].F), R[j].update(i, i, up[i][j].S);
    }
}
void to_thic_cau(){
    cin >> n >> k >> m;
    st_max.init(n);
    st_min.init(n);
    for(int i = 1; i <= m;i++){
        ll a,b; cin >> a >> b;
        if(a < b) st_max.update(a, min(b, a + k - 1), b);
        else st_min.update(max(a - k + 1, b), a, b);
    }
    build();
    cin >> q;
    while(q--){
        ll s,t; cin >> s >> t;
        ll res = 0;
        ll l = s, r = s;
        for(int i = 17; i >= 0;i--){
            ll fl = L[i].get(l, r), fr = R[i].get(l, r);
            if(!(fl <= t && t <= fr)){
                res += (1 << i);
                l = min(l, fl), r = max(r, fr);
            }
        }
        if(res == (1 << 18) - 1){
            cout << -1 << '\n';
        }
        else cout << res + 1 << '\n';
    }
}

signed main()   
{  
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

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