oj.uz

Submission #827340

# Submission time Handle Problem Language Result Execution time Memory
827340 2023-08-16T11:25:44 Z borisAngelov Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 577 ms 43704 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31572 KB Output is correct
2 Correct 11 ms 31572 KB Output is correct
3 Correct 11 ms 31572 KB Output is correct
4 Correct 11 ms 31580 KB Output is correct
5 Correct 11 ms 31552 KB Output is correct
6 Correct 11 ms 31572 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31572 KB Output is correct
2 Correct 11 ms 31572 KB Output is correct
3 Correct 11 ms 31572 KB Output is correct
4 Correct 11 ms 31580 KB Output is correct
5 Correct 11 ms 31552 KB Output is correct
6 Correct 11 ms 31572 KB Output is correct
7 Correct 15 ms 31704 KB Output is correct
8 Correct 16 ms 31684 KB Output is correct
9 Correct 17 ms 31684 KB Output is correct
10 Correct 16 ms 31684 KB Output is correct
11 Correct 16 ms 31700 KB Output is correct
12 Correct 16 ms 31700 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31572 KB Output is correct
2 Correct 11 ms 31572 KB Output is correct
3 Correct 11 ms 31572 KB Output is correct
4 Correct 11 ms 31580 KB Output is correct
5 Correct 11 ms 31552 KB Output is correct
6 Correct 11 ms 31572 KB Output is correct
7 Correct 15 ms 31704 KB Output is correct
8 Correct 16 ms 31684 KB Output is correct
9 Correct 17 ms 31684 KB Output is correct
10 Correct 16 ms 31684 KB Output is correct
11 Correct 16 ms 31700 KB Output is correct
12 Correct 16 ms 31700 KB Output is correct
13 Correct 511 ms 40860 KB Output is correct
14 Correct 532 ms 43116 KB Output is correct
15 Correct 567 ms 43104 KB Output is correct
16 Correct 577 ms 43004 KB Output is correct
17 Correct 528 ms 42892 KB Output is correct
18 Correct 510 ms 43704 KB Output is correct