Submission #1281444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281444		dora_kyu	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	242 ms	21396 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
int a[maxn];
int pt[maxn];
int n, q;
#define endl "\n"


struct Tree
{
    ll nl , nr, nb, nn;

    ll get(){return max({nl, nr, nb, nn});}

} nod[maxn << 2];

void merge(int id, int l, int r)
{
    int m = l + r >> 1;
    int s1 = pt[m], s2 = pt[m+1];
    if( (s1 >= 0 && s2 >= 0) || (s1 <= 0 && s2 <= 0) )
    {
        nod[id].nl = nod[id << 1].nl + nod[id << 1 | 1].nn;
        nod[id].nr = nod[id << 1].nn + nod[id << 1 | 1].nr;
        nod[id].nn = nod[id << 1].nn + nod[id << 1 | 1].nn;
        nod[id].nb = nod[id << 1].nl + nod[id << 1 | 1].nr;
    }
    else
    {
        nod[id].nl = max(nod[id << 1].nl + nod[id << 1 | 1].nl , nod[id << 1].nb + nod[id << 1 | 1].nn ) ;
        nod[id].nr = max(nod[id << 1].nn + nod[id << 1 | 1].nb , nod[id << 1].nr + nod[id << 1 | 1].nr);
        nod[id].nn = max(nod[id << 1].nr + nod[id << 1 | 1].nn , nod[id << 1].nn + nod[id << 1 | 1].nl);
        nod[id].nb = max(nod[id << 1].nl + nod[id << 1 | 1].nb , nod[id << 1].nb + nod[id << 1 | 1].nr);
    }
}

void build(int id ,int l ,int r)
{
    if(l == r)
    {
        nod[id].nr = nod[id].nl = nod[id].nb = 0;
        nod[id].nn = abs(pt[l]);
        return;
    }
    int m = l + r >> 1;
    build(id << 1, l , m);
    build(id << 1 | 1 , m + 1, r);
    merge(id, l , r);
}

void update(int id, int l, int r, int x, int val)
{
    if(l > x || r < x) return;
    if(l == r)
    {
        nod[id].nn = abs(pt[l] + val);
        pt[l] += val;
        return;
    }
    int m = l + r >> 1;
    update(id << 1, l , m , x, val);
    update(id << 1 | 1, m + 1, r, x, val);
    merge(id, l , r);
}

signed main()
{
    cin.tie(nullptr) -> ios_base::sync_with_stdio(0);
    cin >> n >> q;

    for(int i = 1; i <= n; ++i){cin >> a[i];}

    for(int i = 1; i < n; ++i) pt[i] = a[i] - a[i+1];

    build(1, 1,  n- 1);

    for(int i = 1; i <= q; ++i)
    {
        int l, r, x; cin >> l >> r >> x;
        update(1,1,n-1, l - 1 , -x);
        update(1,1,n-1, r, x);
        cout << nod[1].get() << endl;
    }

}

/**
test:
4 3
1 2 3 4
1 2 1
1 1 2
2 3 1

4 3
2 0 2 1
4 4 1
2 2 3
1 3 2
*/

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