Submission #712778

#	Time	Username	Problem	Language	Result	Execution time	Memory
712778		Johann	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	373 ms	34892 KiB

Main

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()

struct item
{
    ll first, last;
    ll dp[2][2];
    item() {}
    item(ll v)
    {
        first = last = v;
        dp[0][0] = 0;      // contains neither first nor last
        dp[0][1] = 0;      // contains not first but last
        dp[1][0] = 0;      // contains first and not last
        dp[1][1] = abs(v); // contains first and last
    }
};

struct segtree
{
    int size;
    vector<item> arr;
    void combine(int x, item &a, item &b)
    {
        arr[x].first = a.first, arr[x].last = b.last;
        for (int i = 0; i < 4; ++i)
        {
            arr[x].dp[i / 2][i % 2] = max(a.dp[i / 2][0] + b.dp[1][i % 2], a.dp[i / 2][1] + b.dp[0][i % 2]);
            if (a.last * b.first > 0)
                arr[x].dp[i / 2][i % 2] = max(arr[x].dp[i / 2][i % 2], a.dp[i / 2][1] + b.dp[1][i % 2]);
        }
    }
    void init(vi &D)
    {
        size = 1;
        while (size < sz(D))
            size *= 2;
        arr.resize(2 * size);
        for (int i = 0; i < sz(D); ++i)
            arr[i + size] = item(D[i]);
        for (int i = size - 1; i > 0; --i)
            combine(i, arr[2 * i], arr[2 * i + 1]);
    }
    void add(int i, ll c)
    {
        add(i, c, 1, 0, size);
    }
    void add(int i, ll c, int x, int lx, int rx)
    {
        if (rx - lx == 1)
        {
            arr[x] = item(arr[x].first + c);
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m)
            add(i, c, 2 * x, lx, m);
        else
            add(i, c, 2 * x + 1, m, rx);
        combine(x, arr[2 * x], arr[2 * x + 1]);
    }
    ll query()
    {
        return arr[1].dp[1][1];
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, Q;
    cin >> N >> Q;
    vi A(N);
    for (int i = 0; i < N; ++i)
        cin >> A[i];

    vi D(N, 0); // D[i] = A[i] - A[i - 1], D[0] = 0;
    for (int i = 1; i < N; ++i)
        D[i] = A[i] - A[i - 1];

    segtree seg;
    seg.init(D);

    for (int q = 0; q < Q; ++q)
    {
        ll l, r, x;
        cin >> l >> r >> x;
        --l;
        if (l > 0)
            seg.add(l, x);
        if (r < sz(D))
            seg.add(r, -x);

        cout << seg.query() << "\n";
    }
}

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