Submission #1249633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249633		norman165	Railway Trip 2 (JOI22_ho_t4)	C++20	16 / 100	1577 ms	589824 KiB

Main

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define yes() cout << "YES\n"
#define no() cout << "NO\n"

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

const int inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 1e7 + 5e6;
const int mod1 = 998244353;
const int mod2 = 1e18 + 1;
const int mod3 = 1e9 + 9;
const int mod4 = 333333333;
const int mod5 = 200000;
const int mod6 = 10007;
const int k = 300;
const int w = 1e5;
const ld EPS = 1e-8;

int LOG = 30;

struct e {
    int t, x;
};

struct segTree2 {
    vector<int> t;
    int n;

    segTree2(int x) {
        n = x;
        t.resize(4 * n, -inf);
    }

    void upd(int v, int l, int r, int idx, int val) {
        if (r - l == 1) {
            t[v] = val;
            return;
        }

        int m = (l + r) / 2;
        if (idx < m) upd(2 * v, l, m, idx, val);
        else upd(2 * v + 1, m, r, idx, val);

        t[v] = max(t[2 * v], t[2 * v + 1]);
    }

    void upd(int idx, int val) {
        upd(1, 0, n, idx, val);
    }

    int get(int v, int l, int r, int ql, int qr) {
        if (l >= qr || r <= ql) return -inf;
        if (ql <= l && r <= qr) return t[v];

        int m = (l + r) / 2;
        return max(get(2 * v, l, m, ql, qr), get(2 * v + 1, m, r, ql, qr));
    }

    int get(int ql, int qr) {
        return get(1, 0, n, ql, qr);
    }
};

struct segTree1 {
    vector<int> t;
    int n;

    segTree1(int x) {
        n = x;
        t.resize(4 * n, inf);
    }

    void upd(int v, int l, int r, int idx, int val) {
        if (r - l == 1) {
            t[v] = val;
            return;
        }

        int m = (l + r) / 2;
        if (idx < m) upd(2 * v, l, m, idx, val);
        else upd(2 * v + 1, m, r, idx, val);

        t[v] = min(t[2 * v], t[2 * v + 1]);
    }

    void upd(int idx, int val) {
        upd(1, 0, n, idx, val);
    }

    int get(int v, int l, int r, int ql, int qr) {
        if (l >= qr || r <= ql) return inf;
        if (ql <= l && r <= qr) return t[v];

        int m = (l + r) / 2;
        return min(get(2 * v, l, m, ql, qr), get(2 * v + 1, m, r, ql, qr));
    }

    int get(int ql, int qr) {
        return get(1, 0, n, ql, qr);
    }
};

void solve() {
    int n, k;
    cin >> n >> k;

    int m;
    cin >> m;

    // vector<vector<int>> dp1(n, vector<int> (n + 1, inf));
    // vector<vector<int>> dp2(n, vector<int> (n + 1, -inf));
    vector<segTree1> dp1;
    vector<segTree2> dp2;
    vector<vector<e>> queries1(n), queries2(n);

    for (int i = 0; i <= n; i++) {
        segTree1 tmp(n);
        dp1.push_back(tmp);
    }

    for (int i = 0; i <= n; i++) {
        segTree2 tmp(n);
        dp2.push_back(tmp);
    }

    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;

        l--, r--;

        if (l <= r) {
            queries1[l].push_back({1, inf});
            if (min(l + k - 1, r) + 1 < n) queries1[min(l + k - 1, r) + 1].push_back({2, inf});
            queries2[l].push_back({1, r});
            if (min(l + k - 1, r) + 1 < n) queries2[min(l + k - 1, r) + 1].push_back({2, r});
        } else {
            queries1[max(r, l - k + 1)].push_back({1, r});
            if (l + 1 < n) queries1[l + 1].push_back({2, r});
            queries2[max(r, l - k + 1)].push_back({1, -inf});
            if (l + 1 < n) queries2[l + 1].push_back({2, -inf});
        }
    }

    multiset<int> prime;
    for (int i = 0; i < n; i++) {
        for (auto& j : queries1[i]) {
            if (j.t == 1) {
                prime.insert(j.x);
            } else {
                prime.extract(j.x);
            }
        }

        if (prime.empty()) continue;
        int l = *prime.begin();
        if (prime.count(inf)) l = min(l, i);
        // dp1[1][i] = l;
        dp1[1].upd(i, l);
    }

    prime.clear();
    for (int i = 0; i < n; i++) {
        for (auto& j : queries2[i]) {
            if (j.t == 1) {
                prime.insert(j.x);
            } else {
                prime.extract(j.x);
            }
        }

        if (prime.empty()) continue;
        int l = *prime.rbegin();
        if (prime.count(-inf)) l = max(l, i);
        // dp2[1][i] = l;
        dp2[1].upd(i, l);
    }

    for (int i = 2; i <= n; i++) {
        for (int j1 = 0; j1 < n; j1++) {
            // for (int j2 = dp1[i - 1][j1]; j2 <= dp2[i - 1][j1]; j2++) {
            //     dp1[i][j1] = min(dp1[i][j1], dp1[1][j2]);
            //     dp2[i][j1] = max(dp2[i][j1], dp2[1][j2]);
            // }

            int ql = dp1[i - 1].get(j1, j1 + 1);
            int qr = dp2[i - 1].get(j1, j1 + 1);

            dp1[i].upd(j1, dp1[1].get(ql, qr + 1));
            dp2[i].upd(j1, dp2[1].get(ql, qr + 1));
        }
    }

    int q;
    cin >> q;

    while (q--) {
        int s, t;
        cin >> s >> t;

        s--, t--;
        int ans = -1;
        for (int i = 1; i <= n; i++) {
            if (dp1[i].get(s, s + 1) <= t && t <= dp2[i].get(s, s + 1)) {
                ans = i;
                break;
            }
        }

        cout << ans << "\n";
    }
}

signed main() {
    // cout.precision(16);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }
}

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