Submission #526857

#	Time	Username	Problem	Language	Result	Execution time	Memory
526857		Jarif_Rahman	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	1149 ms	374564 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int lim = 1e5;

int Log[lim+1];

template<class type, type (*F)(type, type), type def>
struct segtree{
    struct node{
        type sm, lazy_sm;
        node(){
            sm = def, lazy_sm = def;
        }
        node(type x){
            sm = x, lazy_sm = def;
        }
        node operator+(node a){
            return node(F(sm, a.sm));
        }
        void propagate(node a){
            sm = F(sm, a.lazy_sm);
            lazy_sm = F(lazy_sm, a.lazy_sm);
        }
    };

    int k;
    vector<node> v;
    segtree(){}
    segtree(int n){
        k = 1;
        while(k < n) k*=2;
        k*=2;
        v.resize(k);
    }
    void upd(int l, int r, int nd, int a, int b, type x){
        if(a > r || b < l) return;
        if(a >= l && b <= r){
            v[nd].sm = F(v[nd].sm, x);
            v[nd].lazy_sm = F(v[nd].lazy_sm, x);
            return;
        }
        int md = (a+b)/2;
        v[2*nd].propagate(v[nd]);
        v[2*nd+1].propagate(v[nd]);
        v[nd].lazy_sm = def;
        upd(l, r, 2*nd, a, md, x);
        upd(l, r, 2*nd+1, md+1, b, x);
        v[nd] = v[2*nd]+v[2*nd+1];
    }
    void upd(int l, int r, type x){
        upd(l, r, 1, 0, k/2-1, x);
    }
    type get(int l, int r, int nd, int a, int b){
        if(a > r || b < l) return def;
        if(a >= l && b <= r){
            return v[nd].sm;
        }
        int md = (a+b)/2;
        v[2*nd].propagate(v[nd]);
        v[2*nd+1].propagate(v[nd]);
        v[nd].lazy_sm = def;
        type rt = F(get(l, r, 2*nd, a, md), get(l, r, 2*nd+1, md+1, b));
        v[nd] = v[2*nd]+v[2*nd+1];
        return rt;
    }
    type get(int l, int r){
        return get(l, r, 1, 0, k/2-1);
    }
};

template<class type, type (*F)(type, type), type def>
struct sparse_table{
    vector<vector<type>> v;
    sparse_table(){}
    sparse_table(vector<type> _v){
        int n = _v.size();
        int k = 0, p = 1;
        while(p < n) p*=2, k++;
        k++;
        v = vector<vector<type>>(n, vector<type>(k, def));
        for(int i = 0; i < n; i++) v[i][0] = _v[i];
        for(int p = 1; p < k; p++){
            for(int i = 0; i < n; i++){
                v[i][p] = F(v[i][p], v[i][p-1]);
                if(i + (1<<(p-1)) < n) v[i][p] = F(v[i][p], v[i + (1<<(p-1))][p-1]);
            }
        }
    }
    type get(int a, int b){
        int p = Log[b-a+1];
        return F(v[a][p], v[b-(1<<p)+1][p]);
    }
};

int MAX(int a, int b){return max(a, b);}
int MIN(int a, int b){return min(a, b);}

const int K = 18;

int n, m, k;

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

    for(int i = 1; i <= lim; i++) Log[i] = log2(i);

    cin >> n >> k >> m;

    segtree<int, MIN, lim+1> seg1(n);
    segtree<int, MAX, -1> seg2(n);

    vector<sparse_table<int, MIN, lim+1>> s1(K);
    vector<sparse_table<int, MAX, -1>> s2(K);    

    for(int i = 0; i < n; i++) seg1.upd(i, i, i), seg2.upd(i, i, i);

    while(m--){
        int a, b; cin >> a >> b; a--, b--;
        if(a < b) seg2.upd(a, min(a+k-1, b-1), b);
        else{
            swap(a, b);
            seg1.upd(max(b-k+1, a+1), b, a);
        }
    }


    vector<pair<int, int>> nxt(n);
    vector<int> temp1, temp2;
    for(int i = 0; i < n; i++){
        int x = seg1.get(i, i), y = seg2.get(i, i);
        temp1.pb(x);
        temp2.pb(y);
        nxt[i] = {x, y};
    }
    s1[0] = sparse_table<int, MIN, lim+1>(temp1);
    s2[0] = sparse_table<int, MAX, -1>(temp2);

    for(int P = 1; P < K; P++){
        vector<int> temp1, temp2;
        for(int i = 0; i < n; i++)
            temp1.pb(s1[P-1].get(nxt[i].f, nxt[i].sc)),
            temp2.pb(s2[P-1].get(nxt[i].f, nxt[i].sc));
        s1[P] = sparse_table<int, MIN, lim+1>(temp1);
        s2[P] = sparse_table<int, MAX, -1>(temp2);
        for(int i = 0; i < n; i++){
            pair<int, int> p = {s1[P].get(i, i), s2[P].get(i, i)};
            nxt[i] = p;
        }
    }

    int q; cin >> q;
    while(q--){
        int a, b; cin >> a >> b; a--, b--;
        if(a < b){
            if(s2[K-1].get(a, a) < b){
                cout << "-1\n";
                continue;
            }
            pair<int, int> p = {a, a};
            int ans = 0;
            while(1){
                if(s2[0].get(p.f, p.sc) >= b){
                    ans++;
                    break;
                }
                for(int i = K-1; i >= 0; i--){
                    if(s2[i].get(p.f, p.sc) < b){
                        ans+=(1<<i);
                        p = {s1[i].get(p.f, p.sc), s2[i].get(p.f, p.sc)};
                    }
                }
            }
            cout << ans << "\n";
        }
        else{
            swap(a, b);
            if(s1[K-1].get(b, b) > a){
                cout << "-1\n";
                continue;
            }
            pair<int, int> p = {b, b};
            int ans = 0;
            while(1){
                if(s1[0].get(p.f, p.sc) <= a){
                    ans+=1;
                    break;
                }
                for(int i = K-1; i >= 0; i--){
                    if(s1[i].get(p.f, p.sc) > a){
                        ans+=(1<<i);
                        p = {s1[i].get(p.f, p.sc), s2[i].get(p.f, p.sc)};
                    }
                }
            }
            cout << ans << "\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