Submission #883243

#	Time	Username	Problem	Language	Result	Execution time	Memory
883243		boris_mihov	Bigger segments (IZhO19_segments)	C++17	100 / 100	491 ms	58172 KiB

segments

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <vector>
#include <bitset>
#include <queue>
#include <set>

typedef long long llong;
const int MAXN = 500000 + 10;
const llong INF = 1e18;

int n;
llong prefix[MAXN];
struct SegmentTree
{
    struct Node
    {
        int maxDP;
        int lazyDP;
        llong minLast;
        llong lazyLast;

        Node()
        {
            maxDP = 0;
            minLast = INF;
            lazyDP = lazyLast = -1;
        }
    
        friend Node operator + (const Node &left, const Node &right)
        {
            Node res;
            res.maxDP = std::max(left.maxDP, right.maxDP);
            res.minLast = std::min(left.minLast, right.minLast);
            return res;
        }
    };

    Node tree[4*MAXN];
    void push(int node, int l, int r)
    {
        if (tree[node].lazyDP != -1)
        {
            tree[node].maxDP = tree[node].lazyDP;
            if (l < r)
            {
                tree[2*node].lazyDP = tree[node].lazyDP;
                tree[2*node + 1].lazyDP = tree[node].lazyDP;
            }
        }

        if (tree[node].lazyLast != -1)
        {
            tree[node].minLast = tree[node].lazyLast;
            if (l < r)
            {
                tree[2*node].lazyLast = tree[node].lazyLast;
                tree[2*node + 1].lazyLast = tree[node].lazyLast;
            }
        }

        tree[node].lazyDP = -1;
        tree[node].lazyLast = -1;
    }

    void update(int l, int r, int node, int queryL, int queryR, int dpValue, llong lastValue)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazyDP = dpValue;
            tree[node].lazyLast = lastValue;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        update(l, mid, 2*node, queryL, queryR, dpValue, lastValue);
        update(mid + 1, r, 2*node + 1, queryL, queryR, dpValue, lastValue);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    int searchLastDP(int l, int r, int node, int queryL, int queryR, int value)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return -1;
        }

        if (queryL <= l && r <= queryR && tree[node].maxDP > value)
        {
            return -1;
        }

        if (l == r)
        {
            return l;
        }

        int mid = (l + r) / 2;
        int res = searchLastDP(mid + 1, r, 2*node + 1, queryL, queryR, value);
        if (res != -1) return res;
        return searchLastDP(l, mid, 2*node, queryL, queryR, value);
    }

    int searchFirstLast(int l, int r, int node, int queryL, int queryR, llong value)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return -1;
        }

        if (queryL <= l && r <= queryR && tree[node].minLast > value)
        {
            return -1;
        }

        if (l == r)
        {
            return l;
        }

        int mid = (l + r) / 2;
        int res = searchFirstLast(l, mid, 2*node, queryL, queryR, value);
        if (res != -1) return res;
        return searchFirstLast(mid + 1, r, 2*node + 1, queryL, queryR, value);
    }

    Node getNode(int l, int r, int node, int queryPos)
    {
        push(node, l, r);
        if (l == r)
        {
            return tree[node];
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) return getNode(l, mid, 2*node, queryPos);
        else return getNode(mid + 1, r, 2*node + 1, queryPos);
    }

    void update(int l, int r, int dp, llong last)
    {
        update(1, n, 1, l, r, dp, last);
    }

    int searchLastDP(int l, int r, int value)
    {
        return searchLastDP(1, n, 1, l, r, value);
    }

    int searchFirstLast(int l, int r, llong value)
    {
        return searchFirstLast(1, n, 1, l, r, value);
    }
    
    Node getNode(int pos)
    {
        return getNode(1, n, 1, pos);
    }
};

int a[MAXN];
SegmentTree tree;

int searchFirstPrefix(llong value)
{
    int l = 0, r = n + 1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (prefix[mid] < value) l = mid;
        else r = mid;
    }

    return r;
}

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        prefix[i] = prefix[i - 1] + a[i];
    }

    for (int i = 0 ; i <= n ; ++i)
    {
        int dp = 0;
        llong last = 0;
        if (i > 0)
        {
            SegmentTree::Node curr = tree.getNode(i);
            dp = curr.maxDP;
            last = prefix[i] - curr.minLast;
        }
        
        int first = searchFirstPrefix(prefix[i] + last);
        if (first > n) continue;

        int equalDP = tree.searchLastDP(first, n, dp);
        if (first <= equalDP)
        {
            tree.update(first, equalDP, dp + 1, prefix[i]);
        }

        equalDP = std::max(first, equalDP + 1);
        int biggerDP = tree.searchLastDP(first, n, dp + 1);
        if (equalDP <= biggerDP)
        {
            int firstLess = tree.searchFirstLast(equalDP, biggerDP, prefix[i]);
            if (firstLess != -1 && firstLess <= biggerDP)
            {
                tree.update(firstLess, biggerDP, dp + 1, prefix[i]);
            }
        }

    }    

    std::cout << tree.getNode(n).maxDP << '\n';
}

void input()
{
    std::cin >> n;
    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: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27