Submission #516037

#	Time	Username	Problem	Language	Result	Execution time	Memory
516037		KoD	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	1 ms	332 KiB

Main

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using i64 = std::int64_t;

constexpr i64 inf = std::numeric_limits<i64>::max() / 3;

struct Segtree {
    int size, logn;
    vector<array<array<i64, 3>, 3>> data;
    vector<i64> lazy;
    explicit Segtree(const vector<int>& vec) {
        const int n = vec.size();
        while ((1 << logn) < n) {
            logn += 1;
        } 
        size = 1 << logn;
        data.resize(2 * size);
        lazy.resize(size);
        for (int i = 0; i < n; ++i) {
            auto& a = data[i + size];
            for (int j = 0; j < 3; ++j) {
                for (int k = 0; k < 3; ++k) {
                    a[j][k] = -inf;
                }
            }
            a[0][0] = 0;
            a[0][1] = a[1][0] = vec[i];
            a[0][2] = a[2][0] = -vec[i];
        }
        for (int i = size - 1; i > 0; --i) {
            fetch(i);
        }
    }
    void fetch(const int k) {
        auto& a = data[k];
        auto& l = data[2 * k];
        auto& r = data[2 * k + 1];
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                a[i][j] = -inf;
                a[i][j] = std::max(a[i][j], l[i][0] + r[0][j]);
                a[i][j] = std::max(a[i][j], l[i][1] + r[2][j]);
                a[i][j] = std::max(a[i][j], l[i][2] + r[1][j]);
            }
        }
    }
    void apply(const int k, const i64 e) {
        auto& a = data[k];
        a[0][1] += e;
        a[1][0] += e;
        a[0][2] -= e;
        a[2][0] -= e;
        a[1][1] += 2 * e;
        a[2][2] -= 2 * e;
        if (k < size) {
            lazy[k] += e;
        }
    }
    void flush(const int k) {
        if (lazy[k] != 0) {
            apply(2 * k, lazy[k]);
            apply(2 * k + 1, lazy[k]);
            lazy[k] = 0;
        }
    }
    void push(const int k) {
        const int lsb = __builtin_ctz(k);
        for (int d = logn; d > lsb; --d) {
            flush(k >> d);
        }
    }
    void pull(int k) {
        k >>= __builtin_ctz(k);
        while (k > 1) {
            fetch(k >>= 1);
        }
    }
    void operate(int l, int r, const int x) {
        l += size, r += size;
        push(l), push(r);
        const int lc = l, rc = r;
        while (l < r) {
            if (l & 1) apply(l++, x);
            if (r & 1) apply(--r, x);
            l >>= 1, r >>= 1;
        }
        pull(lc), pull(rc);
    }
    i64 fold() const {
        return data[1][0][0];
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, Q;
    std::cin >> N >> Q;
    vector<int> A(N);
    for (auto& x : A) {
        std::cin >> x;
    }
    Segtree seg(A);
    while (Q--) {
        int l, r, x;
        std::cin >> l >> r >> x;
        seg.operate(l - 1, r, x);
        std::cout << seg.fold() << '\n';
    }
    return 0;
}

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