Submission #924598

#	Time	Username	Problem	Language	Result	Execution time	Memory
924598		boris_mihov	Financial Report (JOI21_financial)	C++17	100 / 100	2415 ms	30548 KiB

Main

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <cmath>
#include <set>

typedef long long llong;
const int MAXN = 300000 + 10;
const int INF  = 1e9;

int n, d;
struct SegmentTree
{
    struct Node
    {
        int length;
        int prefixOnes;
        int suffixOnes;
        int maxOnes;
        int maxDP;

        Node()
        {
            prefixOnes = suffixOnes = maxOnes = maxDP = length = 0;
        }

        friend Node operator + (const Node &left, const Node &right)
        {
            Node res;
            res.length = left.length + right.length;
            
            res.prefixOnes = left.prefixOnes;
            if (left.prefixOnes == left.length) res.prefixOnes = left.length + right.prefixOnes;

            res.suffixOnes = right.suffixOnes;
            if (right.suffixOnes == right.length) res.suffixOnes = right.length + left.suffixOnes;
            
            res.maxOnes = left.suffixOnes + right.prefixOnes;
            res.maxOnes = std::max(res.maxOnes, left.maxOnes);
            res.maxOnes = std::max(res.maxOnes, right.maxOnes);
            res.maxDP = std::max(left.maxDP, right.maxDP);
            return res;
        }
    };

    Node tree[4*MAXN];
    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node].length = 1;
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node);
        build(mid + 1, r, 2*node + 1);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    void update(int l, int r, int node, int queryPos, int dpVAL)
    {
        if (l == r)
        {
            tree[node].maxDP = dpVAL;
            tree[node].prefixOnes = 1;
            tree[node].suffixOnes = 1;
            tree[node].maxOnes = 1;
            tree[node].length = 1;
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) update(l, mid, 2*node, queryPos, dpVAL);
        else update(mid + 1, r, 2*node + 1, queryPos, dpVAL);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    Node query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        Node res;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = res + query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) res = res + query(mid + 1, r, 2*node + 1, queryL, queryR);
        return res;
    }

    void build()
    {
        build(1, n, 1);
    }

    void update(int pos, int val)
    {
        update(1, n, 1, pos, val);
    }

    int queryOnes(int l, int r)
    {
        return query(1, n, 1, l, r).maxOnes;
    }

    int queryDP(int l, int r)
    {
        return query(1, n, 1, l, r).maxDP;
    }
};

int a[MAXN];
int dp[MAXN];
int perm[MAXN];
SegmentTree tree;

void solve()
{
    std::iota(perm + 1, perm + 1 + n, 1);
    std::sort(perm + 1, perm + 1 + n, [&](int x, int y)
    {
        return a[x] > a[y] || (a[x] == a[y] && x < y);
    });

    int res = 0;
    tree.build();
    for (int i = 1 ; i <= n ; ++i)
    {
        int l = perm[i], r = n, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (tree.queryOnes(perm[i] + 1, mid) < d) l = mid;
            else r = mid;
        }

        dp[perm[i]] = tree.queryDP(perm[i], r) + 1;
        tree.update(perm[i], dp[perm[i]]);
        res = std::max(res, dp[perm[i]]);
    }

    std::cout << res << '\n';
}

void input()
{
    std::cin >> n >> d;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    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