Submission #1181696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181696		chikien2009	Financial Report (JOI21_financial)	C++20	100 / 100	224 ms	18000 KiB

Main

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

class SEGMENT_TREE
{
private:
    int tree_size;
    vector<int> reset;
    vector<long long> tree;

    inline void Update(int ind, int l, int r, int x, long long v)
    {
        if (r < x || x < l)
        {
            return;
        }
        if (l == r)
        {
            tree[ind] = max(tree[ind], v);
            return;
        }
        if (reset[ind])
        {
            reset[ind << 1] = reset[ind << 1 | 1] = 1;
            tree[ind << 1] = tree[ind << 1 | 1] = -1e18;
            reset[ind] = 0;
        }
        int m = (l + r) >> 1;
        Update(ind << 1, l, m, x, v);
        Update(ind << 1 | 1, m + 1, r, x, v);
        tree[ind] = max(tree[ind << 1], tree[ind << 1 | 1]);
    }
    inline void Reset(int ind, int l, int r, int x, int y)
    {
        if (r < x || y < l)
        {
            return;
        }
        if (x <= l && r <= y)
        {
            tree[ind] = -1e18;
            reset[ind] = true;
            return;
        }
        if (reset[ind])
        {
            reset[ind << 1] = reset[ind << 1 | 1] = 1;
            tree[ind << 1] = tree[ind << 1 | 1] = -1e18;
            reset[ind] = 0;
        }
        int m = (l + r) >> 1;
        Reset(ind << 1, l, m, x, y);
        Reset(ind << 1 | 1, m + 1, r, x, y);
        tree[ind] = max(tree[ind << 1], tree[ind << 1 | 1]);
    }
    inline long long Get(int ind, int l, int r, int x, int y)
    {
        if (r < x || y < l)
        {
            return -1e18;
        }
        if (x <= l && r <= y)
        {
            return tree[ind];
        }
        if (reset[ind])
        {
            reset[ind << 1] = reset[ind << 1 | 1] = 1;
            tree[ind << 1] = tree[ind << 1 | 1] = -1e18;
            reset[ind] = 0;
        }
        int m = (l + r) >> 1;
        return max(Get(ind << 1, l, m, x, y), Get(ind << 1 | 1, m + 1, r, x, y));
    }
    public:
    inline SEGMENT_TREE(int new_size)
    {
        tree_size = new_size;
        tree.clear();
        reset.clear();
        tree.resize(tree_size << 2, -1e18);
        reset.resize(tree_size << 2, 0);
    }
    inline void Update(int x, long long v)
    {
        Update(1, 1, tree_size, x, v);
    }
    inline void Reset(int x, int y)
    {
        Reset(1, 1, tree_size, x, y);
    }
    inline long long Get(int x, int y)
    {
        return Get(1, 1, tree_size, x, y);
    }
} st(300000);

int n, m, d, a[300000], b[300000];
deque<int> dq;

int main()
{
    setup();

    cin >> n >> d;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b, b + n);
    m = unique(b, b + n) - b;
    for (int i = 0; i < n; ++i)
    {
        a[i] = lower_bound(b, b + m, a[i]) - b + 1;
        while (!dq.empty() && dq.front() < i - d)
        {
            st.Reset(a[dq.front()], (dq.size() == 1 ? 300000 : a[dq[1]] - 1));
            dq.pop_front();
        }
        st.Update(a[i], max(1LL, st.Get(1, a[i] - 1) + 1));
        while (!dq.empty() && a[dq.back()] >= a[i])
        {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    cout << st.Get(1, 300000);
    return 0;
}

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