oj.uz

Submission #516041

# Submission time Handle Problem Language Result Execution time Memory
516041 2022-01-20T10:30:08 Z KoD Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 600 ms 49740 KB 
#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) {
        logn = 0;
        const int n = vec.size();
        while ((1 << logn) < n) {
            logn += 1;
        } 
        size = 1 << logn;
        data.resize(2 * size);
        for (auto& a : data) {
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) {
                    a[i][j] = -inf;
                }
            }
        }
        lazy.resize(size);
        for (int i = 0; i < n; ++i) {
            auto& a = data[i + size];
            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] = std::max(l[i][j], r[i][j]);
                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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 5 ms 972 KB Output is correct
8 Correct 5 ms 1048 KB Output is correct
9 Correct 5 ms 956 KB Output is correct
10 Correct 11 ms 960 KB Output is correct
11 Correct 5 ms 972 KB Output is correct
12 Correct 5 ms 972 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 5 ms 972 KB Output is correct
8 Correct 5 ms 1048 KB Output is correct
9 Correct 5 ms 956 KB Output is correct
10 Correct 11 ms 960 KB Output is correct
11 Correct 5 ms 972 KB Output is correct
12 Correct 5 ms 972 KB Output is correct
13 Correct 563 ms 49248 KB Output is correct
14 Correct 465 ms 49196 KB Output is correct
15 Correct 533 ms 49096 KB Output is correct
16 Correct 535 ms 49200 KB Output is correct
17 Correct 600 ms 48996 KB Output is correct
18 Correct 554 ms 49740 KB Output is correct