Submission #1047932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047932		BABY_GANGSTER	Sequence (APIO23_sequence)	C++17	100 / 100	460 ms	80972 KiB

sequence

#include <bits/stdc++.h>
#include "sequence.h"

using namespace std;

struct Segtree
{
    struct Node
    {
        int64_t max_prefix_sum, max_suffix_sum, range_sum;
        Node() { memset(this, 0, sizeof *this); }
    };

    vector<Node> t;
    size_t l;

    Segtree(size_t n)
    {
        l = 1 << (32 - __builtin_clz(n));
        t.resize(2 * l);
    }

    Node combine(Node const &x, Node const &y)
    {
        Node z;
        z.max_prefix_sum = max(x.max_prefix_sum, x.range_sum + y.max_prefix_sum);
        z.max_suffix_sum = max(y.max_suffix_sum, y.range_sum + x.max_suffix_sum);
        z.range_sum = x.range_sum + y.range_sum;
        return z;
    }

    void update(int i, int x)
    {
        i += l;
        t[i].max_prefix_sum = max(0, x);
        t[i].max_suffix_sum = max(0, x);
        t[i].range_sum = x;
        while (i >>= 1)
            t[i] = combine(t[i << 1], t[i << 1 | 1]);
    }

    Node query(int i, int j)
    {
        i += l, j += l;
        Node x = Node(), y = Node();
        while (i <= j)
        {
            if (i & 1)
                x = combine(x, t[i++]);
            if (!(j & 1))
                y = combine(t[j--], y);
            i >>= 1;
            j >>= 1;
        }
        return combine(x, y);
    }
};

int sequence(int N, vector<int> A)
{
    for (int &x : A)
        --x;
    vector<vector<int>> occ(N);
    for (int i = 0; i < N; ++i)
        occ[A[i]].push_back(i);

    Segtree tree_ge(N), tree_le(N);
    for (int i = 0; i < N; ++i)
        tree_ge.update(i, 1), tree_le.update(i, -1);

    int ans = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int &j : occ[i])
            tree_le.update(j, 1);

        auto jt = occ[i].begin();
        for (auto it = occ[i].begin(); it != occ[i].end(); ++it)
        {
            if (jt < it)
                jt = it;
            while (jt + 1 != occ[i].end())
            {
                if ((tree_ge.query(*it, *(jt + 1)).range_sum + tree_ge.query(0, *it - 1).max_suffix_sum +
                     tree_ge.query(*(jt + 1) + 1, N - 1).max_prefix_sum) *
                        (tree_le.query(*it, *(jt + 1)).range_sum + tree_le.query(0, *it - 1).max_suffix_sum +
                         tree_le.query(*(jt + 1) + 1, N - 1).max_prefix_sum) >=
                    0)
                    ++jt;
                else
                    break;
            }
            ans = max(ans, (int)(jt - it + 1));
        }

        for (int &j : occ[i])
            tree_ge.update(j, -1);
    }

    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 7 / 7
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 22 / 22
• Subtask 7: 18 / 18