Submission #1016160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016160		thangdz2k7	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	420 ms	97364 KiB

Main

#include <bits/stdc++.h>
#define seg pair <int, int>
#define l first
#define r second

using namespace std;

const int N = 1e5 + 5;
const int lg = 18;

int n, k, m, q;
seg s[N], rmq[lg][N];

struct segtree{
    seg it[4 * N], lazy[4 * N];

    seg mer(seg a, seg b){
        return seg(min(a.l, b.l), max(a.r, b.r));
    }

    void build(seg *a, int s = 1, int l = 1, int r = n){
        lazy[s] = {n + 1, 0};
        if (l == r){
            it[s] = a[l];
            return;
        }

        int mid = l + r >> 1;
        build(a, 2 * s, l, mid);
        build(a, 2 * s + 1, mid + 1, r);
        it[s] = mer(it[2 * s], it[2 * s + 1]);
    }

    void update(int u, int v, seg val, int s = 1, int l = 1, int r = n){
        if (u <= l && r <= v){
            lazy[s] = mer(lazy[s], val);
            return;
        }

        int mid = l + r >> 1;
        if (mid >= u) update(u, v, val, 2 * s, l, mid);
        if (mid + 1 <= v) update(u, v, val, 2 * s + 1, mid + 1, r);
    }

    void getpoint(int u, seg &ans, int s = 1, int l = 1, int r = n){
        ans = mer(ans, lazy[s]);
        if (l == r){
            ans = mer(ans, it[s]);
            return;
        }

        int mid = l + r >> 1;
        if (mid >= u) getpoint(u, ans, 2 * s, l, mid);
        else getpoint(u, ans, 2 * s + 1, mid + 1, r);
    }

    void getseg(seg p, seg &ans, int s = 1, int l = 1, int r = n){
        if (p.l <= l && r <= p.r){
            ans = mer(ans, it[s]);
            return;
        }

        int mid = l + r >> 1;
        if (mid >= p.l) getseg(p, ans, 2 * s, l, mid);
        if (mid + 1 <= p.r) getseg(p, ans, 2 * s + 1, mid + 1, r);
    }

} tree, tr[lg];

bool check(seg p, int t){
    return p.l <= t && t <= p.r;
}

void solve(){
    cin >> n >> k >> m;
    for (int i = 1; i <= n; ++ i) s[i] = {i, i};
    tree.build(s);
    for (int i = 1, a, b; i <= m; ++ i){
        cin >> a >> b;
        if (a < b) tree.update(a, min(a + k - 1, b - 1), seg(n + 1, b));
        else tree.update(max(a - k + 1, b + 1), a, seg(b, 0));
    }
    for (int i = 1; i <= n; ++ i) rmq[0][i] = {n + 1, 0}, tree.getpoint(i, rmq[0][i]);
    tr[0].build(rmq[0]);
    for (int l = 1; l < lg; ++ l){
        for (int i = 1; i <= n; ++ i) rmq[l][i] = {n + 1, 0}, tr[l - 1].getseg(rmq[l - 1][i], rmq[l][i]);
        tr[l].build(rmq[l]);
    }

    cin >> q;
    while (q --){
        int s, t; cin >> s >> t;
        if (s == t){
            cout << 0 << '\n';
            return;
        }
        if (!check(rmq[lg - 1][s], t)){
            cout << -1 << '\n';
            continue;
        }
        int ans = 0;
        seg cur = {s, s};
        for (int l = lg - 2; l >= 0; -- l){
            seg ck = {n + 1, 0};
            tr[l].getseg(cur, ck);
            if (!check(ck, t)){
                ans += (1 << l);
                cur = ck;
            }
        }
        cout << ans + 1 << '\n';
    }

}

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

    solve();

    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void segtree::build(std::pair<int, int>*, int, int, int)':
Main.cpp:28:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |         int mid = l + r >> 1;
      |                     ^
Main.cpp: In member function 'void segtree::update(int, int, std::pair<int, int>, int, int, int)':
Main.cpp:40:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         int mid = l + r >> 1;
      |                     ^
Main.cpp: In member function 'void segtree::getpoint(int, std::pair<int, int>&, int, int, int)':
Main.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int mid = l + r >> 1;
      |                     ^
Main.cpp: In member function 'void segtree::getseg(std::pair<int, int>, std::pair<int, int>&, int, int, int)':
Main.cpp:63:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         int mid = l + r >> 1;
      |                     ^

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