oj.uz

Submission #511179

# Submission time Handle Problem Language Result Execution time Memory
511179 2022-01-15T10:58:04 Z danikoynov Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 40 ms 2272 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 = 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 13 ms 844 KB Output is correct
8 Correct 17 ms 844 KB Output is correct
9 Correct 11 ms 844 KB Output is correct
10 Correct 11 ms 948 KB Output is correct
11 Correct 11 ms 908 KB Output is correct
12 Correct 14 ms 880 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 13 ms 844 KB Output is correct
8 Correct 17 ms 844 KB Output is correct
9 Correct 11 ms 844 KB Output is correct
10 Correct 11 ms 948 KB Output is correct
11 Correct 11 ms 908 KB Output is correct
12 Correct 14 ms 880 KB Output is correct
13 Runtime error 40 ms 2272 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -