Submission #422677

#	Time	Username	Problem	Language	Result	Execution time	Memory
422677		schse	Financial Report (JOI21_financial)	C++17	100 / 100	2447 ms	34456 KiB

Main

#include <bits/stdc++.h>
#define INF INT32_MAX
using namespace std;

struct segtreenode
{
    int left, midle, right;
    int b, e;
};

segtreenode operator+(segtreenode const &l, segtreenode const &r)
{
    segtreenode res = {l.left, l.right + r.left, r.right, l.b, r.e};
    if (l.left == l.e - l.b)
        res.left += r.left;
    if (r.right == r.e - r.b)
        res.right += l.right;
    res.midle = max(res.midle, r.midle);
    res.midle = max(res.midle, l.midle);
    res.midle = max(res.midle, res.left);
    res.midle = max(res.midle, res.right);
    return res;
}

struct segtree
{
    vector<segtreenode> tree;
    void initial(int N)
    {
        tree.resize(4 * N + 5);
        init(1, 0, N);
    }
    segtreenode init(int index, int b, int e)
    {
        if (e - b == 1)
            return tree[index] = {1, 1, 1, b, e};
        return tree[index] = init(index * 2, b, (b + e) / 2) +
                             init(index * 2 + 1, (b + e) / 2, e);
    }

    segtreenode upd(int index, int b, int e, int p)
    {
        if (e - b == 1 && b == p)
            return tree[index] = {0, 0, 0, b, e};
        if (p < b || e <= p)
            return tree[index];
        return tree[index] = upd(index << 1, b, (b + e) / 2, p) +
                             upd(index * 2 + 1, (b + e) / 2, e, p);
    }

    segtreenode query(int index, int b, int e, int l, int r)
    {
        if (l <= b && e <= r)
            return tree[index];

        if ((b + e) / 2 <= l)
            return query(index * 2 + 1, (b + e) / 2, e, l, r);
        else if (r <= (e + b) / 2)
            return query(index * 2, b, (b + e) / 2, l, r);
        else
            return query(index * 2, b, (b + e) / 2, l, r) + query(index * 2 + 1, (b + e) / 2, e, l, r);
    }
};

struct maxtree
{
    vector<int> tree;
    void initial(int N)
    {
        tree.resize(4 * N + 5);
    }
    int mx(int index, int b, int e, int l, int r)
    {
        if (l <= b && e <= r)
            return tree[index];
        if (r <= b || e <= l)
            return 0;
        return max(mx(index * 2, b, (e + b) / 2, l, r),
                   mx(index * 2 + 1, (e + b) / 2, e, l, r));
    }

    int upd(int index, int b, int e, int p, int v)
    {
        if (b > p || e <= p)
            return tree[index];
        if (b == e - 1)
            return tree[index] = v;
        upd(index * 2, b, (e + b) / 2, p, v);
        upd(index * 2 + 1, (b + e) / 2, e, p, v);
        return tree[index] = max(tree[index * 2], tree[index * 2 + 1]);
    }
};

int main()
{
    int N, D;
    cin >> N >> D;

    vector<pair<int, int>> arr(N);
    segtree stree;
    maxtree mxtree;
    vector<int> varr(N, 0);

    stree.initial(N);
    mxtree.initial(N);

    vector<int> biggest(N + 2, INF);
    vector<int> lastindex(N + 2, -1);

    for (int i = 0; i < N; i++)
    {
        arr[i] = {0, i};
        cin >> arr[i].first;
    }

    sort(arr.begin(), arr.end(), [](pair<int, int> a, pair<int, int> b)
         { return a.first == b.first ? a.second > b.second : a.first < b.first; });

    for (auto [val, pos] : arr)
    {
        int b = 0, e = pos;
        int nv = 0;
        if (pos != 0)
        {

            auto a = stree.query(1, 0, N, 0, pos);
            if (a.midle >= D)
            {
                while (e - b != 1)
                {
                    if (stree.query(1, 0, N, (b + e) / 2, pos).midle >= D)
                        b = (b + e) / 2;
                    else
                        e = (b + e) / 2;
                }
            }
            nv = mxtree.mx(1, 0, N, b, pos);
        }
        mxtree.upd(1, 0, N, pos, nv + 1);
        stree.upd(1, 0, N, pos);
        varr[pos] = nv + 1;
    }

    cout << mxtree.mx(1, 0, N, 0, N);
}

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