Submission #1174679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174679		jioung	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	458 ms	43956 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define eb emplace_back

const int maxn = 2e5 + 5;

int n, q;
ll a[maxn], d[maxn];

struct Node
{
    ll dp[2][2] = {};
    ll bor[2] = {};
    Node() {}
    Node(ll v)
    {
        bor[0] = bor[1] = v;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[0][0] = 0;
        dp[1][1] = abs(v);
    }
    void update(ll v)
    {
        bor[0] += v;
        bor[1] += v;
        dp[1][1] = abs(bor[0]);
    }
};

Node combine(Node t, Node u)
{
    Node ret;
    ret.bor[0] = t.bor[0];
    ret.bor[1] = u.bor[1];
    for (int l = 0; l < 2; l++)
    {
        for (int m = 0; m < 2; m++)
        {
            for (int o = 0; o < 2; o++)
            {
                for (int r = 0; r < 2; r++)
                {
                    if (m && o)
                    {
                        if ((t.bor[1] < 0) == (u.bor[0] < 0))
                            ret.dp[l][r] = max(ret.dp[l][r], t.dp[l][m] + u.dp[o][r]);
                    }
                    else
                    {
                        ret.dp[l][r] = max(ret.dp[l][r], t.dp[l][m] + u.dp[o][r]);
                    }
                }
            }
        }
    }
    return ret;
}

class Seg
{
private:
    vector<Node> st;

public:
    Seg(int sz)
    {
        st.resize(4 * sz + 1);
        build(1, 1, sz);
    }
    void build(int id, int l, int r)
    {
        if (l == r)
        {
            st[id] = Node(d[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(2 * id, l, mid);
        build(2 * id + 1, mid + 1, r);
        st[id] = combine(st[2 * id], st[2 * id + 1]);
    }
    void update(int id, int l, int r, int pos, ll val)
    {
        if (l > pos || r < pos)
            return;
        if (l == r)
        {
            st[id].update(val);
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            update(2 * id, l, mid, pos, val);
        else
            update(2 * id + 1, mid + 1, r, pos, val);
        st[id] = combine(st[2 * id], st[2 * id + 1]);
    }
    ll query()
    {
        return st[1].dp[1][1];
    }
};

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n - 1; i++)
    {
        d[i] = a[i + 1] - a[i];
    }
    Seg segt(n - 1);
    while (q--)
    {
        int l, r;
        ll x;
        cin >> l >> r >> x;
        if (l > 1)
        {
            segt.update(1, 1, n - 1, l - 1, x);
        }
        if (r < n)
        {
            segt.update(1, 1, n - 1, r, -x);
        }
        cout << segt.query() << "\n";
    }
    return 0;
}

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