Submission #712753

#	Time	Username	Problem	Language	Result	Execution time	Memory
712753		Johann	Sjeckanje (COCI21_sjeckanje)	C++14	55 / 110	2060 ms	5032 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()

int k;
struct item
{
    int first, last;
    vvi cnt;
    item()
    {
        first = last = -1;
        cnt.assign(k, vi(k, 0));
    }
};

struct segtree
{
    int size;
    vector<item> arr;
    vi op;
    void create(int x, int c, int len)
    {
        arr[x].first = arr[x].last = c;
        for (int i = 0; i < sz(arr[x].cnt); ++i)
            for (int j = 0; j < sz(arr[x].cnt.front()); ++j)
                arr[x].cnt[i][j] = 0;
        if (c != -1)
            arr[x].cnt[c][c] = len - 1;
    }
    void combine(int x, item &a, item &b)
    {
        arr[x].first = a.first, arr[x].last = b.last;
        for (int i = 0; i < sz(arr[x].cnt); ++i)
            for (int j = 0; j < sz(arr[x].cnt.front()); ++j)
                arr[x].cnt[i][j] = a.cnt[i][j] + b.cnt[i][j];
        if (a.last != -1 && b.first != -1)
            ++arr[x].cnt[a.last][b.first];
    }
    void apply(int x, int len)
    {
        if (op[x] == -1)
            return;
        create(x, op[x], len);
        if (x < size)
            op[2 * x] = op[2 * x + 1] = op[x];
        op[x] = -1;
    }
    void init(string &s)
    {
        size = 1;
        while (size < sz(s))
            size *= 2;
        op.assign(2 * size, -1);
        arr.resize(2 * size);
        for (int i = 0; i < sz(s); ++i)
            create(i + size, s[i] - 'a', 1);
        for (int i = size - 1; i > 0; --i)
            combine(i, arr[2 * i], arr[2 * i + 1]);
    }
    void set(int l, int r, int c)
    {
        set(l, r, c, 1, 0, size);
    }
    void set(int l, int r, int c, int x, int lx, int rx)
    {
        apply(x, rx - lx);
        if (l <= lx && rx <= r)
        {
            op[x] = c;
            apply(x, rx - lx);
            return;
        }
        if (r <= lx || rx <= l)
            return;
        int m = (lx + rx) / 2;
        set(l, r, c, 2 * x, lx, m);
        set(l, r, c, 2 * x + 1, m, rx);
        combine(x, arr[2 * x], arr[2 * x + 1]);
    }
    int query(string &per)
    {
        vi pos(sz(per));
        for (int i = 0; i < sz(per); ++i)
            pos[per[i] - 'a'] = i;
        int ans = 1; // initial thing
        for (int i = 0; i < sz(arr[1].cnt); ++i)
            for (int j = 0; j < sz(arr[1].cnt.front()); ++j)
                if (pos[i] >= pos[j])
                    ans += arr[1].cnt[i][j];
        return ans;
    }
};

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];

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

        vi dp(N, 0);
        dp[1] = abs(D[1]);
        for (int i = 2; i < N; ++i)
        {
            dp[i] = max(dp[i - 2] + abs(D[i]), dp[i - 1]);
            if (D[i] * D[i - 1] > 0)
                dp[i] = max(dp[i], dp[i - 1] + abs(D[i]));
        }
        cout << dp.back() << "\n";
    }
}

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