oj.uz

Submission #712778

# Submission time Handle Problem Language Result Execution time Memory
712778 2023-03-19T21:23:18 Z Johann Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 373 ms 34892 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()

struct item
{
    ll first, last;
    ll dp[2][2];
    item() {}
    item(ll v)
    {
        first = last = v;
        dp[0][0] = 0;      // contains neither first nor last
        dp[0][1] = 0;      // contains not first but last
        dp[1][0] = 0;      // contains first and not last
        dp[1][1] = abs(v); // contains first and last
    }
};

struct segtree
{
    int size;
    vector<item> arr;
    void combine(int x, item &a, item &b)
    {
        arr[x].first = a.first, arr[x].last = b.last;
        for (int i = 0; i < 4; ++i)
        {
            arr[x].dp[i / 2][i % 2] = max(a.dp[i / 2][0] + b.dp[1][i % 2], a.dp[i / 2][1] + b.dp[0][i % 2]);
            if (a.last * b.first > 0)
                arr[x].dp[i / 2][i % 2] = max(arr[x].dp[i / 2][i % 2], a.dp[i / 2][1] + b.dp[1][i % 2]);
        }
    }
    void init(vi &D)
    {
        size = 1;
        while (size < sz(D))
            size *= 2;
        arr.resize(2 * size);
        for (int i = 0; i < sz(D); ++i)
            arr[i + size] = item(D[i]);
        for (int i = size - 1; i > 0; --i)
            combine(i, arr[2 * i], arr[2 * i + 1]);
    }
    void add(int i, ll c)
    {
        add(i, c, 1, 0, size);
    }
    void add(int i, ll c, int x, int lx, int rx)
    {
        if (rx - lx == 1)
        {
            arr[x] = item(arr[x].first + c);
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m)
            add(i, c, 2 * x, lx, m);
        else
            add(i, c, 2 * x + 1, m, rx);
        combine(x, arr[2 * x], arr[2 * x + 1]);
    }
    ll query()
    {
        return arr[1].dp[1][1];
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, Q;
    cin >> N >> Q;
    vi A(N);
    for (int i = 0; i < N; ++i)
        cin >> A[i];

    vi D(N, 0); // D[i] = A[i] - A[i - 1], D[0] = 0;
    for (int i = 1; i < N; ++i)
        D[i] = A[i] - A[i - 1];

    segtree seg;
    seg.init(D);

    for (int q = 0; q < Q; ++q)
    {
        ll l, r, x;
        cin >> l >> r >> x;
        --l;
        if (l > 0)
            seg.add(l, x);
        if (r < sz(D))
            seg.add(r, -x);

        cout << seg.query() << "\n";
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 5 ms 724 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 5 ms 724 KB Output is correct
13 Correct 373 ms 32088 KB Output is correct
14 Correct 345 ms 34248 KB Output is correct
15 Correct 361 ms 34272 KB Output is correct
16 Correct 346 ms 34164 KB Output is correct
17 Correct 355 ms 34272 KB Output is correct
18 Correct 299 ms 34892 KB Output is correct