Submission #1250314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250314		norman165	Railway Trip 2 (JOI22_ho_t4)	C++20	16 / 100	2099 ms	132816 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 = 17;

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<segTree1> dp1;
    vector<segTree2> dp2;
    vector<vector<e>> queries1(n), queries2(n);

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

    for (int i = 0; i < LOG; 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[0].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[0].upd(i, l);
    }

    for (int i = 1; i < LOG; i++) {
        for (int j1 = 0; j1 < n; j1++) {
            int ql = dp1[i - 1].get(j1, j1 + 1);
            int qr = dp2[i - 1].get(j1, j1 + 1);

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

    int q;
    cin >> q;

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

        s--, t--;
        int ans = 0;
        if (!(dp1[LOG - 1].get(s, s + 1) <= t && t <= dp2[LOG - 1].get(s, s + 1))) {
            cout << "-1\n";
            continue;
        }

        int ql = s, qr = s;
        for (int i = LOG - 1; i >= 0; i--) {
            if (!(dp1[i].get(ql, qr + 1) <= t && t <= dp2[i].get(ql, qr + 1))) {
                ans += (1 << i);
                int l1 = dp1[i].get(ql, qr + 1), r1 = dp2[i].get(ql, qr + 1);
                ql = l1, qr = r1;
            }
        }

        cout << ans + 1 << "\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