oj.uz

Submission #680853

# Submission time Handle Problem Language Result Execution time Memory
680853 2023-01-11T22:42:59 Z finn__ Sjeckanje (COCI21_sjeckanje) C++17
0 / 110
 1 ms 212 KB 
#include <bits/stdc++.h>
using namespace std;

bool sign(int x)
{
    return x > 0;
}

struct segtree
{
    vector<array<int, 4>> t;
    vector<array<bool, 2>> y;
    size_t l;

    void transition(size_t i)
    {
        y[i][0] = y[2 * i][0];
        y[i][1] = y[2 * i + 1][1];

        for (size_t j = 0; j < 4; j++)
        {
            int const a1 = t[2 * i][j & 1], a2 = t[2 * i][(j & 1) + 2],
                      b1 = t[2 * i + 1][j & 2], b2 = t[2 * i + 1][(j & 2) + 1];

            t[i][j] = max(a1 + b1, max(a1 + b2, a2 + b1));
            if (y[2 * i][1] == y[2 * i + 1][0])
                t[i][j] = max(t[i][j], a2 + b2);
        }
    }

    segtree(vector<int> const &a)
    {
        l = 1 << (32 - __builtin_clz(a.size() - 1));
        t = vector<array<int, 4>>(2 * l, {0, 0, 0, 0});
        y = vector<array<bool, 2>>(2 * l);

        for (size_t i = 0; i < a.size() - 1; i++)
        {
            t[l + i] = {0, 0, 0, abs(a[i + 1] - a[i])};
            y[l + i][0] = y[l + i][1] = sign(a[i + 1] - a[i]);
        }

        for (size_t i = a.size() - 1; i < l; i++)
            y[l + i][0] = y[l + i][1] = y[l + a.size() - 2][0];

        for (size_t i = l - 1; i; i--)
            transition(i);
    }

    void update(size_t i, int x)
    {
        i += l;

        t[i][3] += y[i][0] ? x : -x;
        if (t[i][3] < 0)
        {
            y[i][0] = y[i][1] = !y[i][0];
            t[i][3] = -t[i][3];
        }

        while (i > 1)
        {
            i >>= 1;
            transition(i);
        }
    }

    int max_value()
    {
        return max(max(t[1][0], t[1][1]), max(t[1][2], t[1][3]));
    }
};

int main()
{
    size_t n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int &x : a)
        cin >> x;

    segtree tree(a);

    for (size_t i = 0; i < q; i++)
    {
        size_t l, r;
        int x;
        cin >> l >> r >> x;
        if (l > 1)
            tree.update(l - 2, x);
        if (r < n)
            tree.update(r - 1, -x);
        cout << tree.max_value() << '\n';
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -