Submission #399006

#	Time	Username	Problem	Language	Result	Execution time	Memory
399006		KoD	Lottery (CEOI18_lot)	C++17	100 / 100	1648 ms	8768 KiB

lot

#include <bits/stdc++.h>

using ll = long long;

template <class T>
using Vec = std::vector<T>;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, L;
    std::cin >> N >> L;
    Vec<int> A(N);
    for (auto& x: A) {
        std::cin >> x;
    }
    int Q;
    std::cin >> Q;
    Vec<int> K(Q);
    for (auto& x: K) {
        std::cin >> x;
    }
    auto cmp = K;
    std::sort(cmp.begin(), cmp.end());
    cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
    const int M = (int) cmp.size();
    Vec<int> lowb(L + 1, M);
    for (int i = 0; i < M; ++i) {
        lowb[cmp[i]] = i;
    }
    for (int i = L - 1; i >= 0; --i) {
        lowb[i] = std::min(lowb[i], lowb[i + 1]);
    }
    Vec<Vec<int>> count(N - L + 1, Vec<int>(M));
    for (int k = 1; k <= N - L; ++k) {
        Vec<int> sum(N - L + 1);
        const auto add = [&](const int l, const int r) {
            sum[l] += 1;
            if (r < N - L) {
                sum[r + 1] -= 1;
            }
        };
        for (int i = 0; i < N - k; ++i) {
            if (A[i] != A[i + k]) {
                add(std::max(0, i - L + 1), std::min(i, N - L - k));
            }
        }
        for (int i = 0; i < N - L; ++i) {
            sum[i + 1] += sum[i];
        }
        for (int i = 0; i <= N - L - k; ++i) {
            const auto k = lowb[sum[i]];
            if (k < M) {
                count[i][k] += 1;
            }
        }
    }
    for (int k = 1; k <= N - L; ++k) {
        Vec<int> sum(N - L + 1);
        const auto add = [&](const int l, const int r) {
            sum[l] += 1;
            if (r < N - L) {
                sum[r + 1] -= 1;
            }
        };
        for (int i = k; i < N; ++i) {
            if (A[i] != A[i - k]) {
                add(std::max(k, i - L + 1), std::min(i, N - L));
            }
        }
        for (int i = 0; i < N - L; ++i) {
            sum[i + 1] += sum[i];
        }
        for (int i = k; i <= N - L; ++i) {
            const auto k = lowb[sum[i]];
            if (k < M) {
                count[i][k] += 1;
            }
        }
    }
    for (int i = 0; i <= N - L; ++i) {
        for (int k = 1; k < M; ++k) {
            count[i][k] += count[i][k - 1];
        }
    }
    for (const auto x: K) {
        const auto k = lowb[x];
        for (int i = 0; i <= N - L; ++i) {
            std::cout << count[i][k] << " \n"[i == N - L];
        }
    }
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20