Submission #690942

#	Time	Username	Problem	Language	Result	Execution time	Memory
690942		yaufung	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	1520 ms	103860 KiB

Main

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

struct node {
    int mn, mx, lazymn, lazymx;
    bool hv;
};
vector<node> tr[20];
vector<pair<int, int>> B;

void build(int lay, int p, int l, int r) {
    if (l == r) {
        tr[lay][p].mn = B[l].first;
        tr[lay][p].mx = B[l].second;
        tr[lay][p].lazymn = tr[lay][p].lazymx = -1;
        tr[lay][p].hv = false;
        return;
    }
    tr[lay][p].hv = true;
    int mid = (l + r) / 2;
    build(lay, p * 2, l, mid);
    build(lay, p * 2 + 1, mid + 1, r);
    tr[lay][p].mn = min(tr[lay][p * 2].mn, tr[lay][p * 2 + 1].mn);
    tr[lay][p].mx = max(tr[lay][p * 2].mx, tr[lay][p * 2 + 1].mx);
    tr[lay][p].lazymn = tr[lay][p].lazymx = -1;
    return;
}

void push(int lay, int p) {
    if (tr[lay][p].lazymn != -1) {
        int me = tr[lay][p].lazymn;
        if (tr[lay][p].hv) {
            if (tr[lay][p * 2].lazymn == -1) tr[lay][p * 2].lazymn = me;
            else tr[lay][p * 2].lazymn = min(tr[lay][p * 2].lazymn, me);
            tr[lay][p * 2].mn = min(tr[lay][p * 2].mn, me);

            if (tr[lay][p * 2 + 1].lazymn == -1) tr[lay][p * 2 + 1].lazymn = me;
            else tr[lay][p * 2 + 1].lazymn = min(tr[lay][p * 2 + 1].lazymn, me);
            tr[lay][p * 2 + 1].mn = min(tr[lay][p * 2 + 1].mn, me);
        }
        tr[lay][p].lazymn = -1;
    }
    if (tr[lay][p].lazymx != -1) {
        int me = tr[lay][p].lazymx;
        if (tr[lay][p].hv) {
            if (tr[lay][p * 2].lazymx == -1) tr[lay][p * 2].lazymx = me;
            else tr[lay][p * 2].lazymx = max(tr[lay][p * 2].lazymx, me);
            tr[lay][p * 2].mx = max(tr[lay][p * 2].mx, me);

            if (tr[lay][p * 2 + 1].lazymx == -1) tr[lay][p * 2 + 1].lazymx = me;
            else tr[lay][p * 2 + 1].lazymx = max(tr[lay][p * 2 + 1].lazymx, me);
            tr[lay][p * 2 + 1].mx = max(tr[lay][p * 2 + 1].mx, me);
        }
        tr[lay][p].lazymx = -1;
    }
    return;
}

void up(int lay, int p, int l, int r, int x, int y, int num, int mode) {
    if (x > r || y < l) return;
    push(lay, p);
    if (x <= l && y >= r) {
        if (mode == -1) {
            tr[lay][p].lazymn = num;
            tr[lay][p].mn = min(tr[lay][p].mn, num);
        }
        else {
            tr[lay][p].lazymx = num;
            tr[lay][p].mx = max(tr[lay][p].mx, num);
        }
        return;
    }
    int mid = (l + r) / 2;
    up(lay, p * 2, l, mid, x, y, num, mode);
    up(lay, p * 2 + 1, mid + 1, r, x, y, num, mode);
    tr[lay][p].mn = min(tr[lay][p * 2].mn, tr[lay][p * 2 + 1].mn);
    tr[lay][p].mx = max(tr[lay][p * 2].mx, tr[lay][p * 2 + 1].mx);
    return;
}

pair<int, int> qu(int lay, int p, int l, int r, int x, int y) {
    if (x > r || y < l) return {1e9, -1};
    push(lay, p);
    if (x <= l && y >= r) {
        return {tr[lay][p].mn, tr[lay][p].mx};
    }
    int mid = (l + r) / 2;
    auto pr1 = qu(lay, p * 2, l, mid, x, y);
    auto pr2 = qu(lay, p * 2 + 1, mid + 1, r, x, y);
    pair<int, int> ans;
    ans.first = min(pr1.first, pr2.first);
    ans.second = max(pr1.second, pr2.second);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    int n, m, k, q, r1, r2;
    cin >> n >> k >> m;
    vector<pair<int, int>> A(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> r1 >> r2;
        A[i] = {r1, r2};
    }
    cin >> q;
    vector<pair<int, int>> Q(q + 1);
    for (int i = 1; i <= q; i++) {
        cin >> r1 >> r2;
        Q[i] = {r1, r2};
    }
    int two = 1, ct = 1;
    while (ct < n) {
        ct *= 2;
        two++;
    }
    for (int i = 0; i <= two; i++) {
        tr[i].reserve(4 * n + 1);
    }
    B.reserve(n + 1);
    for (int i = 1; i <= n; i++) {
        B[i] = {i, i};
    }
    build(0, 1, 1, n);
    for (int i = 1; i <= m; i++) {
        int sl, sr;
        if (A[i].first < A[i].second) {
            sl = A[i].first;
            sr = A[i].first + k - 1;
            up(0, 1, 1, n, sl, sr, A[i].second, 1);
        }
        else {
            sl = A[i].first - k + 1;
            sr = A[i].first;
            up(0, 1, 1, n, sl, sr, A[i].second, -1);
        }
    }
    for (int i = 1; i <= two; i++) {
        int last = i - 1;
        for (int j = 1; j <= n; j++) {
            int l, r;
            auto pr = qu(last, 1, 1, n, j, j);
            l = pr.first;
            r = pr.second;
            pr = qu(last, 1, 1, n, l, r);
            B[j] = pr;
        }
        build(i, 1, 1, n);
    }
    for (int i = 1; i <= q; i++) {
        int ans = 0;
        int l, r;
        l = r = Q[i].first;
        auto pr = qu(two, 1, 1, n, l, r);
        if (Q[i].second < pr.first || Q[i].second > pr.second) {
            ans = -1;
        }
        else {
            for (int j = two - 1; j >= 0; j--) {
                pr = qu(j, 1, 1, n, l, r);
                if (Q[i].second < pr.first || Q[i].second > pr.second) {
                    ans += (1 << j);
                    l = pr.first;
                    r = pr.second;
                }
            }
            ans++;
        }
        cout << ans << "\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