Submission #704996

#	Time	Username	Problem	Language	Result	Execution time	Memory
704996		Cyanmond	Financial Report (JOI21_financial)	C++17	0 / 100	4054 ms	5796 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 main() {
    int N, D;
    std::cin >> N >> D;
    std::vector<int> A(N);
    for (auto &e : A) {
        std::cin >> e;
    }
    {
        // 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<int> keepLimit(N, N);
    for (int i = 0; i < N; ++i) {
        int last = i;
        for (int j = i + 1; j < N; ++j) {
            if (j - last > D) {
                keepLimit[i] = j;
                break;
            }
            if (A[j] <= A[i]) {
                last = j;
            }
        }
    }

    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], f + 1);
        eraseList[keepLimit[i]].push_back(A[i]);
    }
    std::cout << seg.fold(0, N + 1) << std::endl;
}

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