Submission #1028725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028725		tvladm2009	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	960 ms	86024 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int H = 20;

int n, k, m, q;
int treeL[4 * N], treeR[4 * N];
pair<int, int> range[H][N];
int tabL[H][4 * N], tabR[H][4 * N];

void build(int v, int tl, int tr) {
    treeL[v] = tl;
    treeR[v] = tr;
    if (tl < tr) {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
    }
}

void updateR(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) {
        treeR[v] = max(treeR[v], val);
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            updateR(2 * v, tl, tm, pos, val); 
        } else {
            updateR(2 * v + 1, tm + 1, tr, pos, val);
        }
        treeR[v] = max(treeR[2 * v], treeR[2 * v + 1]);
    }
}

void updateL(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) {
        treeL[v] = min(treeL[v], val);
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            updateL(2 * v, tl, tm, pos, val); 
        } else {
            updateL(2 * v + 1, tm + 1, tr, pos, val);
        }
        treeL[v] = min(treeL[2 * v], treeL[2 * v + 1]);
    }
}

int queryR(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl) return 0;
    if (l <= tl && tr <= r) return treeR[v];
    int tm = (tl + tr) / 2;
    return max(queryR(2 * v, tl, tm, l, r), queryR(2 * v + 1, tm + 1, tr, l, r));
}

int queryL(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl) return n;
    if (l <= tl && tr <= r) return treeL[v];
    int tm = (tl + tr) / 2;
    return min(queryL(2 * v, tl, tm, l, r), queryL(2 * v + 1, tm + 1, tr, l, r));
}

void buildH(int v, int tl, int tr, int h) {
    if (tl == tr) {
        treeL[v] = range[h - 1][tl].first;
        treeR[v] = range[h - 1][tr].second;
    } else {
        int tm = (tl + tr) / 2;
        buildH(2 * v, tl, tm, h);
        buildH(2 * v + 1, tm + 1, tr, h);
        treeL[v] = min(treeL[2 * v], treeL[2 * v + 1]);
        treeR[v] = max(treeR[2 * v], treeR[2 * v + 1]);
    }
}

void buildTab(int v, int tl, int tr, int h) {
    if (tl == tr) {
        tabL[h][v] = range[h][tl].first;
        tabR[h][v] = range[h][tl].second;
    } else {
        int tm = (tl + tr) / 2;
        buildTab(2 * v, tl, tm, h);
        buildTab(2 * v + 1, tm + 1, tr, h);
        tabL[h][v] = min(tabL[h][2 * v], tabL[h][2 * v + 1]);
        tabR[h][v] = max(tabR[h][2 * v], tabR[h][2 * v + 1]);
    }
}

int queryTabL(int v, int tl, int tr, int l, int r, int h) {
    if (l > tr || r < tl) return n;
    if (l <= tl && tr <= r) return tabL[h][v];
    int tm = (tl + tr) / 2;
    return min(queryTabL(2 * v, tl, tm, l, r, h), queryTabL(2 * v + 1, tm + 1, tr, l, r, h));
}

int queryTabR(int v, int tl, int tr, int l, int r, int h) {
    if (l > tr || r < tl) return 0;
    if (l <= tl && tr <= r) return tabR[h][v];
    int tm = (tl + tr) / 2;
    return max(queryTabR(2 * v, tl, tm, l, r, h), queryTabR(2 * v + 1, tm + 1, tr, l, r, h));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> m;
    vector<pair<int, int>> trains;
    for (int i = 1; i <= m; ++i) {
        int a, b;
        cin >> a >> b;
        trains.push_back({a, b});
    }
    build(1, 1, n);
    for (int i = 0; i < m; ++i) {
        int a = trains[i].first;
        int b = trains[i].second;
        if (a < b) {
            updateR(1, 1, n, a, b);
        } else {
            updateL(1, 1, n, a, b);
        }
    }
    for (int i = 1; i <= n; ++i) {
        range[0][i].first = queryL(1, 1, n, i, min(i + k - 1, n));
        range[0][i].second = queryR(1, 1, n, max(1, i - k + 1), i); 
    }
    for (int h = 1; h < 20; ++h) {
        buildH(1, 1, n, h);
        for (int i = 1; i <= n; ++i) {
            int l = range[h - 1][i].first;
            int r = range[h - 1][i].second;
            range[h][i].first = queryL(1, 1, n, l, r);
            range[h][i].second = queryR(1, 1, n, l, r);
        }
    }
    for (int h = 0; h < 20; ++h) buildTab(1, 1, n, h);

    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        int l = a, r = a;
        int ans = 0;
        for (int h = 19; h >= 0; --h) {
            int ll = queryTabL(1, 1, n, l, r, h);
            int rr = queryTabR(1, 1, n, l, r, h);
            if (b < ll || b > rr) {
                l = ll;
                r = rr;
                ans += (1 << h);
            }
        }
        int ll = queryTabL(1, 1, n, l, r, 0);
        int rr = queryTabR(1, 1, n, l, r, 0);
        if (b < ll || b > rr) {
            cout << -1 << "\n";
            continue;
        }
        cout << ans + 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