Submission #916745

#	Time	Username	Problem	Language	Result	Execution time	Memory
916745		FilipL	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	350 ms	42484 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define rep(a, b) for (int a = 0; a < (b); a++)
#define rep1(a, b) for (int a = 1; a <= (b); a++)
#define all(x) (x).begin(), (x).end()
#define printrange(s, e) {for (auto it = s; it < e; it++) {cout << *it << ' ';} cout << '\n';}
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9 + 7;

#define LOCAL false

const int MAX_LOGN = 17;
const int MAX_N = 1<<MAX_LOGN; // >10^5
const int MAX_M = 2e5 + 7;
int n, k, m, q;

const int TREE_SIZE = MAX_N<<1;
int ftree[TREE_SIZE];
int btree[TREE_SIZE];
void fpushrange(int l, int r, int val) {
    for (l += MAX_N, r += MAX_N+1; l<r; l>>=1, r>>=1) {
        if (l&1) {
            ftree[l] = max(ftree[l], val);
            l++;
        }
        if (r&1) {
            r--;
            ftree[r] = max(ftree[r], val);
        }
    }
}
void bpushrange(int l, int r, int val) {
    for (l += MAX_N, r += MAX_N+1; l<r; l>>=1, r>>=1) {
        if (l&1) {
            btree[l] = min(btree[l], val);
            l++;
        }
        if (r&1) {
            r--;
            btree[r] = min(btree[r], val);
        }
    }
}
int fgetmax(int idx) {
    int mx = INT_MIN;
    for (int v = idx+MAX_N; v >= 1; v>>=1) mx = max(mx, ftree[v]);
    return mx;
}
int bgetmin(int idx) {
    int mn = INT_MAX;
    for (int v = idx+MAX_N; v >= 1; v>>=1) mn = min(mn, btree[v]);
    return mn;
}

pii ivl[MAX_LOGN+1][TREE_SIZE];
pii* curtree;
void build() {
    int l, r;
    for (int v = MAX_N-1; v >= 1; v--) {
        l = v*2; r = v*2+1;
        curtree[v].first = min(curtree[l].first, curtree[r].first);
        curtree[v].second = max(curtree[l].second, curtree[r].second);
    }
}
pii getrange(int l, int r) {
    int s = INT_MAX;
    int e = INT_MIN;
    for (l += MAX_N, r += MAX_N+1; l<r; l>>=1, r>>=1) {
        if (l&1) {
            s = min(s, curtree[l].first);
            e = max(e, curtree[l].second);
            l++;
        }
        if (r&1) {
            r--;
            s = min(s, curtree[r].first);
            e = max(e, curtree[r].second);
        }
    }
    return {s, e};
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (LOCAL) {
        ignore=freopen("io/in", "r", stdin);
        ignore=freopen("io/out", "w", stdout);
    }

    rep(i, TREE_SIZE) {
        ftree[i] = INT_MIN;
        btree[i] = INT_MAX;
    }

    cin >> n >> k;
    cin >> m;
    int a, b;
    rep(i, m) {
        cin >> a >> b;
        a--; b--;
        if (a < b) fpushrange(a, min(a+k-1, b-1), b);
        else bpushrange(max(a-k+1, b+1), a, b);
    }
        
    curtree = ivl[0];
    rep(i, n) curtree[MAX_N+i] = {min(i, bgetmin(i)), max(i, fgetmax(i))};
    build();
    rep1(i, MAX_LOGN) {
        rep(v, MAX_N) {
            curtree = ivl[i-1];
            auto [l, r] = ivl[i-1][MAX_N+v];
            ivl[i][MAX_N+v] = getrange(l, r);
        }
        curtree = ivl[i];
        build();
    }

    cin >> q;
    rep(i, q) {
        int l, r;
        int ans = 0;
        bool can = false;
        cin >> a >> b;
        a--; b--;
        l = a; r = a;
        for (int p = MAX_LOGN; p >= 0; p--) {
            curtree = ivl[p];
            auto [l2, r2] = getrange(l, r);
            if (!(l2 <= b && b <= r2)) {
                l = l2;
                r = r2;
                ans |= (1<<p);
            } else can = true;
        }
        if (can) cout << ans+1 << '\n';
        else cout << "-1\n";
    }

    return 0;
}

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