제출 #704656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
704656		Cyanmond	Lottery (CEOI18_lot)	C++17	100 / 100	1648 ms	27596 KiB

lot

#include <bits/stdc++.h>

constexpr int B = 1300;

int main() {
    int N, L;
    std::cin >> N >> L;
    const int U = N - L + 1;
    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());

    std::vector<std::vector<short>> addVal(Q + 1, std::vector<short>(U));
    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 l = 0; l < U; l += B) {
        const int r = std::min(l + B, U);
        const int lw = r - l;
        const int V = (int)A.size() - L + 1;
        const int T = std::min(lw, V);
        if (T <= 0) {
            break;
        }
        std::vector<std::vector<short>> countSim(T, std::vector<short>(V, 0));

        for (int w = 1; w < V; ++w) {
            std::vector<int> ids;
            for (int i = 0; i < std::min((int)A.size() - w, T + L - 1); ++i) {
                if (A[i] == A[i + w]) {
                    ids.push_back(i);
                }
            }

            auto add = [&](int a, int b) {
                int x = std::max(0, -a);
                if (a + x < T and a + w + x < V) --countSim[a + x][a + w + x];
                if (b < T and b + w < V) ++countSim[b][b + w];
            };
            for (const int i : ids) {
                add(i - L + 1, i + 1);
            }
        }
        for (int i = 0; i < T; ++i) {
            for (int j = 0; j < V; ++j) {
                if (i != 0 and j != 0) {
                    countSim[i][j] += countSim[i - 1][j - 1];
                }
            }
        }
        for (int i = 0; i < T; ++i) {
            for (int j = i + 1; j < V; ++j) {
                ++addVal[level[countSim[i][j] + L]][i + l];
                ++addVal[level[countSim[i][j] + L]][j + l];
            }
        }

        A.erase(A.begin(), A.begin() + lw);
    }
    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: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20