Submission #1157428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157428		woohyun_jng	Railway Trip 2 (JOI22_ho_t4)	C++20	0 / 100	2103 ms	179952 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAX = 300000;
const int MAX_LOG = 20;
const int INF = 0x3f3f3f3f3f3f3f3f;

int A[MAX], B[MAX], tree[2][MAX_LOG][MAX * 4], lazy[2][MAX_LOG][MAX * 4], L[MAX][MAX_LOG], R[MAX][MAX_LOG];

void init(int t, int idx, int n, int s, int e) {
    if (s == e)
        tree[t][idx][n] = t ? 0 : INF;
    else {
        int m = s + e >> 1;
        init(t, idx, n << 1, s, m), init(t, idx, n << 1 | 1, m + 1, e);
        if (t == 0)
            tree[t][idx][n] = min(tree[t][idx][n << 1], tree[t][idx][n << 1 | 1]);
        else
            tree[t][idx][n] = max(tree[t][idx][n << 1], tree[t][idx][n << 1 | 1]);
    }
}

void lazy_update(int t, int idx, int n, int s, int e) {
    if (lazy[t][idx][n] == 0 || lazy[t][idx][n] == INF)
        return;
    if (t)
        tree[t][idx][n] = max(tree[t][idx][n], lazy[t][idx][n]);
    else
        tree[t][idx][n] = min(tree[t][idx][n], lazy[t][idx][n]);
    if (s ^ e) {
        if (t == 0) {
            lazy[t][idx][n << 1] = min(lazy[t][idx][n << 1], lazy[t][idx][n]);
            lazy[t][idx][n << 1 | 1] = min(lazy[t][idx][n << 1 | 1], lazy[t][idx][n]);
        } else {
            lazy[t][idx][n << 1] = max(lazy[t][idx][n << 1], lazy[t][idx][n]);
            lazy[t][idx][n << 1 | 1] = max(lazy[t][idx][n << 1 | 1], lazy[t][idx][n]);
        }
    }
    lazy[t][idx][n] = t ? 0 : INF;
}

int query(int t, int idx, int n, int s, int e, int l, int r) {
    lazy_update(t, idx, n, s, e);
    if (r < s || e < l)
        return t ? 0 : INF;
    else if (l <= s && e <= r)
        return tree[t][idx][n];
    else {
        int m = s + e >> 1;
        if (t == 0)
            return min(query(t, idx, n << 1, s, m, l, r), query(t, idx, n << 1 | 1, m + 1, e, l, r));
        else
            return max(query(t, idx, n << 1, s, m, l, r), query(t, idx, n << 1 | 1, m + 1, e, l, r));
    }
}

void update(int t, int idx, int n, int s, int e, int l, int r, int v) {
    lazy_update(t, idx, n, s, e);
    if (r < s || e < l)
        return;
    else if (l <= s && e <= r)
        lazy[t][idx][n] = v, lazy_update(t, idx, n, s, e);
    else {
        int m = s + e >> 1;
        update(t, idx, n << 1, s, m, l, r, v), update(t, idx, n << 1 | 1, m + 1, e, l, r, v);
        if (t == 0)
            tree[t][idx][n] = min(tree[t][idx][n << 1], tree[t][idx][n << 1 | 1]);
        else
            tree[t][idx][n] = max(tree[t][idx][n << 1], tree[t][idx][n << 1 | 1]);
    }
}

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

    int N, K, M, Q, S, T, X, Y, x, y, ans = 0, st, en, md;

    cin >> N >> K >> M;

    init(0, 0, 1, 1, N), init(1, 0, 1, 1, N);

    for (int i = 1; i <= N; i++) {
        update(0, 0, 1, 1, N, i, i, i);
        update(1, 0, 1, 1, N, i, i, i);
    }

    for (int i = 1; i <= M; i++) {
        cin >> A[i] >> B[i];
        if (A[i] <= B[i]) {
            X = min(B[i] - 1, A[i] + K - 1);
            update(1, 0, 1, 1, N, A[i], X, B[i]);
        } else {
            X = max(B[i] + 1, A[i] - K + 1);
            update(0, 0, 1, 1, N, X, A[i], B[i]);
        }
    }

    for (int i = 1; i <= N; i++) {
        L[i][0] = query(0, 0, 1, 1, N, i, i);
        R[i][0] = query(1, 0, 1, 1, N, i, i);
    }

    init(0, 0, 1, 1, N), init(1, 0, 1, 1, N);
    for (int i = 1; i <= N; i++) {
        update(0, 0, 1, 1, N, i, i, L[i][0]);
        update(1, 0, 1, 1, N, i, i, R[i][0]);
    }

    for (int i = 1; i < MAX_LOG; i++) {
        init(0, i, 1, 1, N), init(1, i, 1, 1, N);

        for (int j = 1; j <= N; j++) {
            L[j][i] = query(0, i - 1, 1, 1, N, L[j][i - 1], R[j][i - 1]);
            R[j][i] = query(1, i - 1, 1, 1, N, L[j][i - 1], R[j][i - 1]);

            update(0, i, 1, 1, N, j, j, L[j][i]);
            update(1, i, 1, 1, N, j, j, R[j][i]);
        }
    }

    cin >> Q;
    while (Q--) {
        cin >> S >> T;

        st = 1, en = M, ans = -1;
        while (st <= en) {
            md = st + en >> 1;
            X = S, Y = S;

            for (int i = MAX_LOG - 1; i >= 0; i--) {
                if (!(md & (1ll << i)))
                    continue;
                x = query(0, i, 1, 1, N, X, Y);
                y = query(1, i, 1, 1, N, X, Y);
                X = x, Y = y;
            }

            if (X <= T && T <= Y)
                ans = md, en = md - 1;
            else
                st = md + 1;
        }

        cout << ans << '\n';
    }

    return 0;
}

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