Submission #704651

#	Time	Username	Problem	Language	Result	Execution time	Memory
704651		Cyanmond	Lottery (CEOI18_lot)	C++17	45 / 100	38 ms	65536 KiB

lot

#include <bits/stdc++.h>

int main() {
    int N, L;
    std::cin >> N >> L;
    std::vector<int> A(N);
    for (auto &e : A) {
        std::cin >> e;
    }
    int Q;
    std::cin >> Q;
    std::vector<std::pair<int, int>> K(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> K[i].first;
        K[i].second = i;
    }
    std::sort(K.begin(), K.end());
    const int U = N - L + 1;
    std::vector<std::vector<short>> countSim(U, std::vector<short>(U, 0));

    for (int w = 1; w < U; ++w) {
        std::vector<int> ids;
        for (int i = 0; i < N - w; ++i) {
            if (A[i] == A[i + w]) {
                ids.push_back(i);
            }
        }

        auto add = [&](int l, int r) {
            int x = std::max(0, -l);
            --countSim[l + x][l + w + x];
            if (r + w < U) ++countSim[r][r + w];
        };
        for (const int i : ids) {
            add(i - L + 1, i + 1);
        }
    }
    for (int i = 0; i < U; ++i) {
        for (int j = 0; j < U; ++j) {
            if (i != 0 and j != 0) {
                countSim[i][j] += countSim[i - 1][j - 1];
            }
        }
    }
    std::vector<std::vector<short>> addVal(Q + 1, std::vector<short>(N));
    std::vector<int> level(L + 1);
    for (int i = 0; i <= L; ++i) {
        int c = 0;
        while (c != Q and K[c].first < i) {
            ++c;
        }
        level[i] = c;
    }
    for (int i = 0; i < U; ++i) {
        for (int j = i + 1; j < U; ++j) {
            ++addVal[level[countSim[i][j] + L]][i];
            ++addVal[level[countSim[i][j] + L]][j];
        }
    }
    std::vector<std::vector<short>> answer(Q, std::vector<short>(N));
    std::vector<short> nowData(U, 0);
    for (int i = 0; i < Q; ++i) {
        for (int j = 0; j < U; ++j) {
            nowData[j] += addVal[i][j];
        }
        answer[K[i].second] = nowData;
    }
    for (const auto &vec : answer) {
        for (int i = 0; i < U; ++i) {
            std::cout << vec[i] << (i == U - 1 ? '\n' : ' ');
        }
    }
}

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