Submission #511179

#	Time	Username	Problem	Language	Result	Execution time	Memory
511179		danikoynov	Sjeckanje (COCI21_sjeckanje)	C++14	55 / 110	40 ms	2272 KiB

Main

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const ll inf = 1e18;
const int maxn = 3010;

struct node
{
    ll dp[4];
    ll fr, bk;

    node()
    {
        dp[0] = dp[1] = dp[2] = dp[3] = 0;
        fr = 0;
        bk = 0;
    }

    node(int _fr, int _bk)
    {
        fr = _fr;
        bk = _bk;
    }
};

bool diff(ll x, ll y)
{
    if (x > 0 && y < 0)
        return true;
    if (x < 0 && y > 0)
        return true;
    return false;
}
node merge_node(node nd1, node nd2)
{
    node nd;
    nd.fr = nd1.fr;
    nd.bk = nd2.bk;

    if (diff(nd1.bk, nd2.fr))
    {
        for (int i = 0; i < 4; i ++)
            for (int j = 0; j < 4; j ++)
            {
                if (i % 2 == 1 && j / 2 == 1)
                {
                    continue;
                }

                int mask = (i / 2) * 2 + (j % 2);
                nd.dp[mask] = max(nd.dp[mask], nd1.dp[i] + nd2.dp[j]);
            }
    }
    else
    {
        nd.dp[0] = max(nd1.dp[0], nd1.dp[1]) + max(nd2.dp[0], nd2.dp[2]);
        nd.dp[1] = max(nd1.dp[0], nd1.dp[1]) + max(nd2.dp[1], nd2.dp[3]);
        nd.dp[2] = max(nd1.dp[2], nd1.dp[3]) + max(nd2.dp[0], nd2.dp[2]);
        nd.dp[3] = max(nd1.dp[2], nd1.dp[3]) + max(nd2.dp[1], nd2.dp[3]);
    }

    return nd;
}

node tree[4 * maxn];
ll a[maxn], d[maxn];
void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root].bk = tree[root].fr = d[left];
        tree[root].dp[1] = tree[root].dp[2] = -inf;
        tree[root].dp[0] = 0;
        tree[root].dp[3] = abs(d[left]);
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);


    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

void update(int root, int left, int right, int idx)
{
    if (left == right)
    {
        tree[root].bk = tree[root].fr = d[left];
        tree[root].dp[1] = tree[root].dp[2] = -inf;
        tree[root].dp[0] = 0;
        tree[root].dp[3] = abs(d[left]);
        return;
    }

    int mid = (left + right) / 2;
    if (idx <= mid)
        update(root * 2, left, mid, idx);
    else
        update(root * 2 + 1, mid + 1, right, idx);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
int n, q;

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

    for (int i = 1; i < n; i ++)
        d[i] = a[i + 1] - a[i];


    build_tree(1, 1, n - 1);
    for (int i = 1; i <= q; i ++)
    {
        int l, r, x;
        cin >> l >> r >> x;
        if (l != 1)
        {
            d[l - 1] += x;
            update(1, 1, n - 1, l - 1);
        }
        if (r != n)
        {
            d[r] -= x;
            update(1, 1, n - 1, r);
        }

        ll ans = 0;
        for (int j = 0; j < 4; j ++)
            ans = max(ans, tree[1].dp[j]);
        cout << ans << endl;


    }

}

int main()
{
    solve();
    return 0;
}
/**
4 3
4 3 3 4

*/

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