Submission #827340

#	Time	Username	Problem	Language	Result	Execution time	Memory
827340		borisAngelov	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	577 ms	43704 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;

int n, q;
int a[maxn];

long long delta[maxn];

bool is_diff(long long x, long long y)
{
    if (x > 0 && y < 0)
    {
        return true;
    }

    if (x < 0 && y > 0)
    {
        return true;
    }

    return false;
}

struct segment_tree
{
    struct state
    {
        int first;
        int last;
        long long dp[2][2];

        state()
        {
            first = 0;
            last = 0;

            for (int i = 0; i <= 1; ++i)
            {
                for (int j = 0; j <= 1; ++j)
                {
                    dp[i][j] = 0;
                }
            }
        }
    };

    state tree[4 * maxn];

    state combine(const state& left_child, const state& right_child)
    {
        state result;

        result.first = left_child.first;
        result.last = right_child.last;

        for (int first_l = 0; first_l <= 1; ++first_l)
        {
            for (int last_l = 0; last_l <= 1; ++last_l)
            {
                for (int first_r = 0; first_r <= 1; ++first_r)
                {
                    for (int last_r = 0; last_r <= 1; ++last_r)
                    {
                        if (last_l == 1 && first_r == 1)
                        {
                            if (is_diff(left_child.last, right_child.first) == false)
                            {
                                result.dp[first_l][last_r] = max(result.dp[first_l][last_r], left_child.dp[first_l][last_l] + right_child.dp[first_r][last_r]);
                            }
                        }
                        else
                        {
                            result.dp[first_l][last_r] = max(result.dp[first_l][last_r], left_child.dp[first_l][last_l] + right_child.dp[first_r][last_r]);
                        }
                    }
                }
            }
        }

        return result;
    }

    void build(int node, int l, int r)
    {
        if (l == r)
        {
            tree[node].first = delta[l];
            tree[node].last = delta[l];
            tree[node].dp[0][0] = 0;
            tree[node].dp[0][1] = 0;
            tree[node].dp[1][0] = 0;
            tree[node].dp[1][1] = abs(delta[l]);
            return;
        }

        int mid = (l + r) / 2;

        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);

        tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
    }

    void update(int node, int l, int r, int pos, long long val)
    {
        if (l == r)
        {
            tree[node].first = val;
            tree[node].last = val;
            tree[node].dp[0][0] = 0;
            tree[node].dp[0][1] = 0;
            tree[node].dp[1][0] = 0;
            tree[node].dp[1][1] = abs(val);
            return;
        }

        int mid = (l + r) / 2;

        if (pos <= mid)
        {
            update(2 * node, l, mid, pos, val);
        }
        else
        {
            update(2 * node + 1, mid + 1, r, pos, val);
        }

        tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
    }

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

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

segment_tree tree;

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

int main()
{
    fastIO();

    cin >> n >> q;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }

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

    tree.build();

    for (int i = 1; i <= q; ++i)
    {
        int l, r, x;
        cin >> l >> r >> x;

        if (l != 1)
        {
            delta[l - 1] += x;
            tree.update(l - 1, delta[l - 1]);
        }

        if (r != n)
        {
            delta[r] -= x;
            tree.update(r, delta[r]);
        }

        long long ans = 0;

        for (int fr = 0; fr <= 1; ++fr)
        {
            for (int sc = 0; sc <= 1; ++sc)
            {
                ans = max(ans, tree.tree[1].dp[fr][sc]);
            }
        }

        cout << ans << "\n";
    }

    return 0;
}

/*
4 3
1 2 3 4
1 2 1
1 1 2
2 3 1

4 1
1 2 3 4
1 2 1
*/

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55