Submission #71639705

---

Source Code Expand

import std;

void main () {
    int N, K;
    readln.read(N, K);
    auto P = readln.split.to!(int[]);
    P[] -= 1;

    // Q[i] := 値iがある位置
    auto Q = new int[](N);
    foreach (i; 0 .. N) {
        Q[P[i]] = i;
    }

    auto swm = new SlidingWindowMinimum!(int)(Q);
    auto qs = new Tuple!(int, int)[](N - K + 1);

    foreach (i; 0 .. N - K + 1) {
        qs[i] = tuple(i, i + K);
    }
    auto minIdx = swm.solve(qs);
    auto maxIdx = swm.solve!"a > b"(qs);

    int ans = int.max;
    foreach (i; 0 .. N - K + 1) {
        ans = min(ans, Q[maxIdx[i]] - Q[minIdx[i]]);
    }

    writeln(ans);
}

class SlidingWindowMinimum (T) {
    T[] A;
    this (T[] A_) {
        A = A_;
    }

    int[] solve (alias cmp = "a < b") (const Tuple!(int, int)[] queries) {
        alias cmpfun = binaryFun!(cmp);
        auto ret = new int[](queries.length);
        auto st = DList!(T)();

        int l = 0;
        int r = 0;
        foreach (i; 0 .. queries.length) {
            while (r < queries[i][1]) {
                while (!st.empty() && !cmpfun(A[st.front()], A[r])) {
                    st.removeFront();
                }
                st.insertFront(r);
                r++;
            }

            while (l < queries[i][0]) {
                if (st.back() == l) {
                    st.removeBack();
                }
                l++;
            }

            ret[i] = st.empty() ? -1 : st.back();
        }

        return ret;
    }
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

Submission Info

Compile Error

/home/runner/.dub/packages/mir-algorithm/3.20.4/mir-algorithm/source/mir/serde.d(52,9): Deprecation: alias this for classes/interfaces is deprecated

Judge Result