oj.uz

Submission #680855

# Submission time Handle Problem Language Result Execution time Memory
680855 2023-01-11T22:48:23 Z finn__ Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 754 ms 28992 KB 
#include <bits/stdc++.h>
using namespace std;

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

struct segtree
{
    vector<array<int64_t, 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++)
        {
            int64_t 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<int64_t> const &a)
    {
        l = 1 << (32 - __builtin_clz(a.size() - 1));
        t = vector<array<int64_t, 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, int64_t 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);
        }
    }

    int64_t 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<int64_t> a(n);
    for (int64_t &x : a)
        cin >> x;

    segtree tree(a);

    for (size_t i = 0; i < q; i++)
    {
        size_t l, r;
        int64_t 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 9 ms 724 KB Output is correct
8 Correct 10 ms 724 KB Output is correct
9 Correct 10 ms 852 KB Output is correct
10 Correct 10 ms 696 KB Output is correct
11 Correct 10 ms 720 KB Output is correct
12 Correct 10 ms 724 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 9 ms 724 KB Output is correct
8 Correct 10 ms 724 KB Output is correct
9 Correct 10 ms 852 KB Output is correct
10 Correct 10 ms 696 KB Output is correct
11 Correct 10 ms 720 KB Output is correct
12 Correct 10 ms 724 KB Output is correct
13 Correct 751 ms 28428 KB Output is correct
14 Correct 754 ms 28520 KB Output is correct
15 Correct 705 ms 28408 KB Output is correct
16 Correct 718 ms 28364 KB Output is correct
17 Correct 728 ms 28252 KB Output is correct
18 Correct 673 ms 28992 KB Output is correct