Submission #705015

#	Time	Username	Problem	Language	Result	Execution time	Memory
705015		Cyanmond	Financial Report (JOI21_financial)	C++17	100 / 100	606 ms	46996 KiB

Main

#include <bits/stdc++.h>

constexpr int inf = 1 << 30;

class SegTree {
    int n, size;
    std::vector<int> data;
    void update(int i) {
        data[i] = std::max(data[2 * i], data[2 * i + 1]);
    }

    public:
    SegTree(int n_) : n(n_) {
        size = 1;
        while (size < n) size *= 2;
        data.assign(2 * size, -inf);
    }

    void set(int i, int v) {
        i += size;
        data[i] = v;
        while (i != 1) {
            i /= 2;
            update(i);
        }
    }

    int fold(int l, int r) {
        int res = -inf;
        for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = std::max(res, data[l++]);
            if (r & 1) res = std::max(res, data[--r]);
        }
        return res;
    }

    int get(int i) {
        return data[i + size];
    }
};

int solve(int D, std::vector<int> A) {
    const int N = (int)A.size();
    {
        // press
        auto B = A;
        std::sort(B.begin(), B.end());
        B.erase(std::unique(B.begin(), B.end()), B.end());
        for (auto &e : A) e = (int)(std::lower_bound(B.begin(), B.end(), e) - B.begin()) + 1;
    }

    std::vector<std::vector<int>> posList(N + 1);
    for (int i = 0; i < N; ++i) {
        posList[A[i]].push_back(i);
    }
    std::vector<int> keepLimit(N, N);
    std::set<int> sids;
    for (int i = D; i < N; ++i) sids.insert(i);
    for (int v = 1; v <= N; ++v) {
        for (const int i : posList[v]) {
            // [i + 1, i + D]
            auto itr = sids.upper_bound(i);
            while (itr != sids.end() and *itr <= i + D) {
                itr = sids.erase(itr);
            }
        }
        for (const int i : posList[v]) {
            auto itr = sids.upper_bound(i);
            if (itr != sids.end()) {
                keepLimit[i] = *itr;
            }
        }
    }

    SegTree seg(N + 1);
    seg.set(0, 0);
    std::vector<std::vector<int>> eraseList(N + 1);
    for (int i = 0; i < N; ++i) {
        for (const int j : eraseList[i]) {
            seg.set(j, -inf);
        }
        const int f = seg.fold(0, A[i]);
        seg.set(A[i], std::max(seg.get(A[i]), f + 1));
        eraseList[keepLimit[i]].push_back(A[i]);
    }
    return seg.fold(0, N + 1);
}

int solveNaive(int D, std::vector<int> A) {
    const int N = (int)A.size();
    int answer = 1;
    for (int bits = 0; bits < (1 << N); ++bits) {
        int last = -1;
        if (not(bits & (1 << (N - 1)))) {
            continue;
        }
        int res = 0, ma = -1;
        for (int i = 0; i < N; ++i) {
            if (bits & (1 << i)) {
                if (last == -1) {
                    last = i;
                } else {
                    if (i - last > D) {
                        res = -1;
                        break;
                    }
                }
                last = i;
                if (A[i] > ma) {
                    ++res;
                    ma = A[i];
                }
            }
        }
        answer = std::max(answer, res);
    }
    return answer;
}

int main() {
    int N, D;
    std::cin >> N >> D;
    std::vector<int> A(N);
    for (auto &e : A) {
        std::cin >> e;
    }
    std::cout << solve(D, A) << std::endl;
    /*
    int N = 15;
    int cas = 100;
    std::mt19937 mt(100);
    std::uniform_int_distribution dist(1, N);
    while (cas--) {
        std::vector<int> A(N);
        for (auto &e : A) e = dist(mt);
        int D = dist(mt);
        const int a = solveNaive(D, A), b = solve(D, A);
        if (a != b) {
            std::cout << D << std::endl;
            for (const auto e : A) std::cout << e << ' ';
            std::cout << std::endl;
        }
    }*/
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35