Submission #535358

#	Time	Username	Problem	Language	Result	Execution time	Memory
535358		KoD	AAQQZ (JOI15_aaqqz)	C++17	100 / 100	1225 ms	44920 KiB

aaqqz

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

void setmax(int& x, const int y) {
    if (x < y) {
        x = y;
    }
}

int solve(const int N, const int C, const vector<int>& A) {
    vector<vector<int>> idx(C);
    for (int i = 0; i < N; ++i) {
        idx[A[i]].push_back(i);
    }
    vector<int> taken(C);
    const auto reset = [&](const int lowb) {
        for (int i = 0; i < C; ++i) {
            taken[i] = std::lower_bound(idx[i].begin(), idx[i].end(), lowb) - idx[i].begin();
        }
    };
    const auto empty = [&](const int x) {
        return taken[x] == (int)idx[x].size();
    };
    const auto pop = [&](const int x) {
        return idx[x][taken[x]++];
    };

    int ret = 0;
    vector add(N, vector<int>(N + 2));

    const auto process = [&](const int left, const int right, const int except) {
        reset(right);
        vector<char> type(N);
        vector<pair<int, int>> consider;
        for (int i = left - 1, last = 0; i >= 0; --i) {
            if (A[i] < last or empty(A[i])) {
                break;
            }
            const int j = pop(A[i]);
            type[j] = 1;
            consider.emplace_back(i, j);
            last = A[i];
        }

        for (int i = right; i < N; ++i) {
            if (type[i] == 0 and A[i] == except) {
                type[i] = 2;
            }
        }

        vector<int> bad(C + 1, N);
        for (int i = right; i < N; ++i) {
            if (type[i] == 0 and bad[A[i] + 1] == N) {
                bad[A[i] + 1] = i;
            }
        }
        for (int i = 0; i < C; ++i) {
            bad[i + 1] = std::min(bad[i + 1], bad[i]);
        }
        
        vector<int> sum(N + 1);
        for (int i = 0; i < N; ++i) {
            sum[i + 1] = sum[i] + (type[i] == 2);
        }

        vector<int> nearest(N + 1, N);
        for (int i = N - 1; i >= 0; --i) {
            nearest[i] = type[i] != 2 ? i : nearest[i + 1];
        }

        int must = right;
        for (const auto& [l, r] : consider) {
            setmax(must, r + 1);
            if (bad[A[l]] < must) {
                break;
            }
            setmax(ret, 2 * (left - l) + sum[bad[A[l]]] - sum[right] + right - left);
            if (sum[must] - sum[right] + left - l == must - right) {
                add[l][must] += 1;
                add[l][nearest[must] + 1] -= 1;
            }
        }
    };

    for (int i = 1; i < N; ++i) {
        process(i, i, A[i - 1]);
        for (int j = i; j < N; ++j) {
            if (A[i - 1] > A[j]) {
                process(i, i, A[j]);
                break;
            }
        }
    }

    vector make(N, vector<char>(N + 1));

    for (int i = 0; i < N; ++i) {
        int l = i, r = i + 1;
        while (l > 0 and r < N and A[l - 1] == A[r]) {
            l -= 1;
            r += 1;
        }
        process(l, r, -1);
        make[i][i + 1] = true;
    }
    for (int i = 1; i < N; ++i) {
        int l = i, r = i;
        while (l > 0 and r < N and A[l - 1] == A[r]) {
            l -= 1;
            r += 1;
        }
        process(l, r, -1);
        make[i][i] = true;
    }

    for (int i = 0; i < N; ++i) {
        int sum = 0;
        for (int j = 0; j <= N; ++j) {
            sum += add[i][j];
            make[i][j] = sum > 0;
        }
    }
    for (int len = 1; len < N; ++len) {
        for (int l = 1; l + len < N; ++l) {
            const int r = l + len;
            if (make[l][r] and A[l - 1] == A[r]) {
                make[l - 1][r + 1] = true;
            }
        }
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (make[j][i]) {
                setmax(ret, i - j);
            }
        }
    }
    return ret;
}

int main() {
    int N, C;
    std::cin >> N >> C;
    vector<int> A(N), freq(C);
    for (auto& x : A) {
        std::cin >> x;
        x -= 1;
        freq[x] += 1;
    }
    int ans = *std::max_element(freq.begin(), freq.end());
    setmax(ans, solve(N, C, A));
    std::reverse(A.begin(), A.end());
    for (auto& x : A) {
        x = C - x - 1;
    }
    setmax(ans, solve(N, C, A));
    std::cout << ans << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90