Submission #1111784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111784		I_FloPPed21	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	2 ms	4432 KiB

Main

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
const int N=2e5+1;
int v[N],a[N],n,m;
int dp[4*N][2][2],lazy[4*N];//practic intervalu nostru are capete sau n-are capete
int borders[4*N][2];//0 e left 1 e right
void merge(int nod_a,int nod_b,int nod_c)//vrem sa dam merge la nod_a si nod_b in nod_c
{
    borders[nod_c][0]=borders[nod_a][0];
    borders[nod_c][1]=borders[nod_b][1];
    dp[nod_c][0][0]=0;
    dp[nod_c][0][1]=0;
    dp[nod_c][1][0]=0;
    dp[nod_c][1][1]=0;
    for(int k=0; k<2; k++)
    {
        for(int d=0; d<2; d++)
        {
            for(int mid=0; mid<2; mid++)
            {
                for(int mid2=0; mid2<2; mid2++)
                {
                    if(mid&&mid2)
                    {
                        if((borders[nod_a][1]>=0)==(borders[nod_b][0]>=0))
                        {
                            dp[nod_c][k][d]=max(dp[nod_c][k][d],dp[nod_a][k][mid]+dp[nod_b][mid2][d]);
                        }
                    }
                    else
                    {
                        dp[nod_c][k][d]=max(dp[nod_c][k][d],dp[nod_a][k][mid]+dp[nod_b][mid2][d]);
                    }
                }
            }
        }
    }
}
void update(int nod,int st,int dr,int poz,int val)
{
    if(st==dr)
    {
        borders[nod][0]+=val;
        borders[nod][1]+=val;
        dp[nod][1][1]=abs(borders[nod][0]);
        dp[nod][0][0]=0;
        dp[nod][1][0]=0;
        dp[nod][0][1]=0;
    }
    else
    {
        int mij=(st+dr)/2;
        if(poz<=mij)
        {
            update(nod*2,st,mij,poz,val);
        }
        else
        {
            update(nod*2+1,mij+1,dr,poz,val);
        }
        merge(nod*2,nod*2+1,nod);
    }
}
void read()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    for(int i=1; i<=n-1; i++)
    {
        a[i]=v[i+1]-v[i];
    }
    for(int i=1; i<=n-1; i++)
    {
        update(1,1,n,i,a[i]);
    }
}
void solve()
{
    for(int i=1; i<=m; i++)
    {
        int l,r,x;
        cin>>l>>r>>x;
        if(l-1>=1)
        {
            update(1,1,n,l-1,x);
        }
        if(r<n)
        {
            update(1,1,n,r,-x);
        }
        cout<<dp[1][1][1]<<'\n';
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    solve();
    return 0;
}

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