oj.uz

Submission #511180

# Submission time Handle Problem Language Result Execution time Memory
511180 2022-01-15T10:58:24 Z danikoynov Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 1076 ms 50792 KB 
/**
 ____ ____ ____ ____ ____ ____
||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 = 2e5 + 10;

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37836 KB Output is correct
2 Correct 17 ms 37804 KB Output is correct
3 Correct 17 ms 37820 KB Output is correct
4 Correct 18 ms 37836 KB Output is correct
5 Correct 16 ms 37836 KB Output is correct
6 Correct 19 ms 37836 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37836 KB Output is correct
2 Correct 17 ms 37804 KB Output is correct
3 Correct 17 ms 37820 KB Output is correct
4 Correct 18 ms 37836 KB Output is correct
5 Correct 16 ms 37836 KB Output is correct
6 Correct 19 ms 37836 KB Output is correct
7 Correct 29 ms 37948 KB Output is correct
8 Correct 29 ms 37896 KB Output is correct
9 Correct 28 ms 37896 KB Output is correct
10 Correct 29 ms 37904 KB Output is correct
11 Correct 30 ms 37964 KB Output is correct
12 Correct 35 ms 37876 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37836 KB Output is correct
2 Correct 17 ms 37804 KB Output is correct
3 Correct 17 ms 37820 KB Output is correct
4 Correct 18 ms 37836 KB Output is correct
5 Correct 16 ms 37836 KB Output is correct
6 Correct 19 ms 37836 KB Output is correct
7 Correct 29 ms 37948 KB Output is correct
8 Correct 29 ms 37896 KB Output is correct
9 Correct 28 ms 37896 KB Output is correct
10 Correct 29 ms 37904 KB Output is correct
11 Correct 30 ms 37964 KB Output is correct
12 Correct 35 ms 37876 KB Output is correct
13 Correct 982 ms 49232 KB Output is correct
14 Correct 934 ms 50184 KB Output is correct
15 Correct 968 ms 50100 KB Output is correct
16 Correct 941 ms 50072 KB Output is correct
17 Correct 965 ms 50048 KB Output is correct
18 Correct 1076 ms 50792 KB Output is correct