Submission #556122

#	Time	Username	Problem	Language	Result	Execution time	Memory
556122		Alexandruabcde	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	548 ms	36624 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
constexpr LL INF = 1LL * 1e16;
constexpr int NMAX = 2e5 + 5;

LL val[NMAX];
struct Node {
    LL dp[2][2];
};

LL modul (LL x) {
    if (x < 0) x = -x;
    return x;
}

void CompareBest (LL &x, LL y) {
    x = max(x, y);
}

class SegmentTree {
private:
    vector <Node> arb;
    int sz;

    void Comb (int nod, int a, int b) {
        int st = 2 * nod, dr = 2 * nod + 1;
        int mij = (a + b) / 2;

        for (int caz_st = 0; caz_st < 2; ++ caz_st)
            for (int caz_dr = 0; caz_dr < 2; ++ caz_dr) {
                arb[nod].dp[caz_st][caz_dr] = -INF;

                CompareBest(arb[nod].dp[caz_st][caz_dr], arb[st].dp[caz_st][0] + arb[dr].dp[0][caz_dr]);
                CompareBest(arb[nod].dp[caz_st][caz_dr], arb[st].dp[caz_st][0] + arb[dr].dp[1][caz_dr]);
                CompareBest(arb[nod].dp[caz_st][caz_dr], arb[st].dp[caz_st][1] + arb[dr].dp[0][caz_dr]);

                if (val[mij] * val[mij+1] >= 0)
                    CompareBest(arb[nod].dp[caz_st][caz_dr], arb[st].dp[caz_st][1] + arb[dr].dp[1][caz_dr]);
            }
    }

    void Update (int nod, int a, int b, int poz, LL val) {
        if (a == b) {
            arb[nod].dp[0][0] = 0;
            arb[nod].dp[1][1] = modul(val);
            arb[nod].dp[1][0] = arb[nod].dp[0][1] = -INF;
            return;
        }

        int mij = (a + b) / 2;

        if (poz <= mij) Update(2*nod, a, mij, poz, val);
        else Update(2*nod+1, mij+1, b, poz, val);

        Comb(nod, a, b);
    }

public:
    void Init (int Size) {
        arb.resize(4*Size+4);
        for (int i = 1; i <= 4 * Size; ++ i ) {
            arb[i].dp[0][0] = arb[i].dp[1][1] = 0;
            arb[i].dp[1][0] = arb[i].dp[0][1] = -INF;
        }
        sz = Size;
    }

    void Update (int pos, LL value) {
        Update(1, 1, sz, pos, value);
    }

    LL Best () {
        LL ans = 0;
        CompareBest(ans, arb[1].dp[0][0]);
        CompareBest(ans, arb[1].dp[1][0]);
        CompareBest(ans, arb[1].dp[0][1]);
        CompareBest(ans, arb[1].dp[1][1]);

        return ans;
    }
};

SegmentTree SGT;
int N, Q;

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> Q;

    for (int i = 1; i <= N; ++ i )
        cin >> val[i];

    for (int i = 1; i < N; ++ i )
        val[i] = val[i] - val[i+1];
    val[N] = 0;
    SGT.Init(N-1);

    for (int i = 1; i < N; ++ i )
        SGT.Update(i, val[i]);
}

void Solve () {
    for (; Q; -- Q ) {
        int l, r;
        LL x;
        cin >> l >> r >> x;

        val[l-1] -= x;
        val[r] += x;

        if (l-1 > 0) SGT.Update(l-1, val[l-1]);
        if (r < N) SGT.Update(r, val[r]);

        cout << SGT.Best() << '\n';
    }
}

int main () {
    Read();
    Solve();

    return 0;
}

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