Submission #1249374

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

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

    int m;
    cin >> m;

    vector<vector<pair<int, int>>> dp(n, vector<pair<int, int>> (k + 1, {inf, -inf}));

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

        l--, r--;

        if (l <= 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 {
            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);
            }
        }
    }

    for (int i = 2; i <= k; 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 <= k; 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: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13