Submission #526899

#	Time	Username	Problem	Language	Result	Execution time	Memory
526899		eecs	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	269 ms	237872 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;
int n, K, m, q, mx[maxn], mn[maxn];
int f[18][maxn], g[18][maxn], st1[18][18][maxn], st2[18][18][maxn];

int main() {
    scanf("%d %d %d", &n, &K, &m);
    iota(mx + 1, mx + n + 1, 1);
    iota(mn + 1, mn + n + 1, 1);
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d %d", &a, &b);
        if (a < b) mx[a] = max(mx[a], b);
        else mn[a] = min(mn[a], b);
    }
    deque<int> Q;
    for (int i = n; i; i--) {
        while (!Q.empty() && mn[Q.back()] > mn[i]) Q.pop_back();
        Q.push_back(i);
        while (Q.front() >= i + K) Q.pop_front();
        f[0][i] = mn[Q.front()];
    }
    Q.clear();
    for (int i = 1; i <= n; i++) {
        while (!Q.empty() && mx[Q.back()] < mx[i]) Q.pop_back();
        Q.push_back(i);
        while (Q.front() <= i - K) Q.pop_front();
        g[0][i] = mx[Q.front()];
    }
    auto qmin = [&](int st[18][maxn], int l, int r) {
        int k = __lg(r - l + 1);
        return min(st[k][l], st[k][r - (1 << k) + 1]);
    };
    auto qmax = [&](int st[18][maxn], int l, int r) {
        int k = __lg(r - l + 1);
        return max(st[k][l], st[k][r - (1 << k) + 1]);
    };
    for (int k = 0; k < 18; k++) {
        if (k) {
            for (int i = 1; i <= n; i++) {
                f[k][i] = qmin(st1[k - 1], f[k - 1][i], g[k - 1][i]);
                g[k][i] = qmax(st2[k - 1], f[k - 1][i], g[k - 1][i]);
            }
        }
        for (int i = 1; i <= n; i++) {
            st1[k][0][i] = f[k][i], st2[k][0][i] = g[k][i];
        }
        for (int i = 1; i < 18; i++) {
            for (int j = 1; j + (1 << i) - 1 <= n; j++) {
                st1[k][i][j] = min(st1[k][i - 1][j], st1[k][i - 1][j + (1 << (i - 1))]);
                st2[k][i][j] = max(st2[k][i - 1][j], st2[k][i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    scanf("%d", &q);
    while (q--) {
        int s, t;
        scanf("%d %d", &s, &t);
        int l = s, r = s, ans = 0;
        for (int i = 17; ~i; i--) {
            int _l = qmin(st1[i], l, r), _r = qmax(st2[i], l, r);
            if (_r < t || _l > t) l = _l, r = _r, ans |= 1 << i;
        }
        printf("%d\n", ans > n ? -1 : ans + 1);
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d %d %d", &n, &K, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
Main.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d %d", &s, &t);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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