Submission #1249377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249377		norman165	Railway Trip 2 (JOI22_ho_t4)	C++20	8 / 100	2098 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;
};

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

    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[i][1] = 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[i][1] = l;
    }

    for (int i = 2; i <= n; i++) {
        for (int j1 = 0; j1 < n; j1++) {
            for (int j2 = dp1[j1][i - 1]; j2 <= dp2[j1][i - 1]; j2++) {
                dp1[j1][i] = min(dp1[j1][i], dp1[j2][1]);
                dp2[j1][i] = max(dp2[j1][i], dp2[j2][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[s][i] <= t && t <= dp2[s][i]) {
                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: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13