Submission #1249376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249376		norman165	Railway Trip 2 (JOI22_ho_t4)	C++20	8 / 100	2099 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<pair<int, int>>> dp(n, vector<pair<int, int>> (n + 1, {inf, -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});
            // for (int j = l; j <= min(l + k - 1, r); j++) {
            //     dp[j][1].first = min(dp[j][1].first, j);
            //     dp[j][1].second = max(dp[j][1].second, 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});
            // for (int j = max(r, l - k + 1); j <= l; j++) {
            //     dp[j][1].first = min(dp[j][1].first, r);
            //     dp[j][1].second = max(dp[j][1].second, j);
            // }
        }
    }

    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);
        dp[i][1].first = 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);
        dp[i][1].second = l;
    }

    for (int i = 2; i <= n; i++) {
        for (int j1 = 0; j1 < n; j1++) {
            for (int j2 = dp[j1][i - 1].first; j2 <= dp[j1][i - 1].second; j2++) {
                dp[j1][i].first = min(dp[j1][i].first, dp[j2][1].first);
                dp[j1][i].second = max(dp[j1][i].second, dp[j2][1].second);
            }
        }
    }

    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 (dp[s][i].first <= t && t <= dp[s][i].second) {
                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