Submission #1192446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192446		alir3za_zar3	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	465 ms	21388 KiB

Main

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define     int     long long

const int mxN = 2e5+7;
int n,q , a[mxN];

struct SEGMENT 
{
    struct NODE
    {
        int val[2][2] = {};
    } T[4*mxN],base;

    tuple<int,int,int> info 
    (int node , int l , int r)
    {
        int o=l+r>>1 , lc=node<<1 , rc=lc+1;
        return {o , lc , rc};
    }
    void build 
    (int node=1 , int l=1 , int r=n)
    {
        if (l+1 == r)
        {
            T[node].val[0][0] = abs(a[l]);
            T[node].val[0][1] = T[node].val[1][0] = 0;
            T[node].val[1][1] = 0;
            return;
        }
        auto [o , lc , rc] = info(node , l , r);
        build (lc , l , o);
        build (rc , o , r);
        for (int ll=0; ll<=1; ll++)
            for (int rr=0; rr<=1; rr++)
                for (int lr=0; lr<=1; lr++)
                    for (int rl=0; rl<=1; rl++)
                    {
                        if (lr>0 or rl>0)
                            T[node].val[ll][rr] = max(T[node].val[ll][rr],
                                                      T[lc].val[ll][lr]+T[rc].val[rl][rr]);
                        else if (a[o-1]<0 and a[o]<0)
                            T[node].val[ll][rr] = max(T[node].val[ll][rr],
                                                      T[lc].val[ll][lr]+T[rc].val[rl][rr]);
                        else if (a[o-1]>0 and a[o]>0)
                            T[node].val[ll][rr] = max(T[node].val[ll][rr],
                                                      T[lc].val[ll][lr]+T[rc].val[rl][rr]);
                    }
    }
    void update 
    (int id , int node=1 , int l=1 , int r=n)
    {
        T[node] = base;
        if (l+1 == r)
        {
            T[node].val[0][0] = abs(a[l]);
            T[node].val[0][1] = T[node].val[1][0] = 0;
            T[node].val[1][1] = 0;
            return;
        }
        auto [o , lc , rc] = info(node , l , r);
        if (id < o) update(id , lc , l , o);
        else update(id , rc , o , r);
        for (int ll=0; ll<=1; ll++)
            for (int rr=0; rr<=1; rr++)
                for (int lr=0; lr<=1; lr++)
                    for (int rl=0; rl<=1; rl++)
                    {
                        if (lr>0 or rl>0)
                            T[node].val[ll][rr] = max(T[node].val[ll][rr],
                                                      T[lc].val[ll][lr]+T[rc].val[rl][rr]);
                        else if (a[o-1]<0 and a[o]<0)
                            T[node].val[ll][rr] = max(T[node].val[ll][rr],
                                                      T[lc].val[ll][lr]+T[rc].val[rl][rr]);
                        else if (a[o-1]>0 and a[o]>0)
                            T[node].val[ll][rr] = max(T[node].val[ll][rr],
                                                      T[lc].val[ll][lr]+T[rc].val[rl][rr]);
                    }
    }
} segmenT;

signed main ()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
    
    cin >> n >> q;
    for (int i=1; i<=n; i++)
        cin >> a[i];
    for (int i=1; i<n; i++)
        a[i] = a[i+1]-a[i];

    segmenT.build();
    while (q--)
    {
        int l,r,v; cin >> l >> r >> v;
        if (l > 1)
            a[l-1]+=v , segmenT.update(l-1);
        if (r < n)
            a[r]-=v , segmenT.update(r);

        int out = 0;
        for (int i=0; i<=1; i++)
            for (int j=0; j<=1; j++)
                out = max(out , segmenT.T[1].val[i][j]);
        cout << out << '\n';
    }
}

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