Submission #831276

#	Time	Username	Problem	Language	Result	Execution time	Memory
831276		12345678	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	505 ms	36616 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int nx=2e5+5, sx=2, inf=1e9;
int n, q, idx, df[nx], v[nx], l, r, x;

struct segtree
{
    struct mat:array<array<ll, sx>, sx>
    {
        mat() {
            for (int i=0; i<sx; i++) for (int j=0; j<sx; j++) (*this)[i][j]=-inf;
        }
        mat(int idx)
        {
            (*this)[1][1]=-inf; (*this)[0][1]=0;
            if ((df[idx]^df[idx-1])>=0) (*this)[0][0]=abs(df[idx]), (*this)[1][0]=-inf;
            else (*this)[0][0]=0, (*this)[1][0]=abs(df[idx]);
        }
        friend mat operator*(const mat A, const mat B)
        {
            mat res;
            for (int i=0; i<sx; i++) for (int j=0; j<sx; j++) for (int k=0; k<sx; k++) res[i][j]=max(A[i][k]+B[k][j], res[i][j]);
            return res;
        }
    } d[4*nx];
    void build(int l, int r,  int i)
    {
        if (l==r) return void(d[i]=mat(l));
        int md=(l+r)/2;
        build(md+1, r, 2*i+1);
        build(l, md, 2*i);
        d[i]=d[2*i]*d[2*i+1];
    }
    void update(int l, int r, int i, int idx)
    {
        if (idx<l||r<idx) return;
        if (l==r) return void(d[i]=mat(l));
        int md=(l+r)/2;
        update(l, md, 2*i, idx);
        update(md+1, r, 2*i+1, idx);
        d[i]=d[2*i]*d[2*i+1];
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    for (int i=1; i<=n; i++) cin>>v[i], df[i]=v[i]-v[i-1];
    s.build(2, n, 1);
    while (q--)
    {
        cin>>l>>r>>x;
        df[l]+=x; df[r+1]-=x;
        s.update(2, n, 1, l);
        s.update(2, n, 1, l+1);
        s.update(2, n, 1, r+1);
        s.update(2, n, 1, r+2);
        cout<<max(s.d[1][0][0], s.d[1][1][0])<<'\n';
    }
}

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