Submission #1030116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030116		parsadox2	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	5 ms	12892 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
int n , a[N] , d[N] , q;

struct SEG{
    struct NODE{
        int dp[2][2];
        NODE()
        {
            memset(dp , 0 , sizeof dp);
        }
    };
    NODE t[N << 2];
    NODE Merge(NODE lc , NODE rc , int lim)
    {
        NODE res;
        if((d[lim] < 0 && d[lim - 1] > 0) || (d[lim] > 0 && d[lim - 1] < 0))
        {
            for(int i = 0 ; i < 2 ; i++)  for(int j = 0 ; j < 2 ; j++)
                res.dp[i][j] = max(lc.dp[i][0] + rc.dp[1][j] , lc.dp[i][1] + rc.dp[0][j]);
        }
        else
        {
            for(int i = 0 ; i < 2 ; i++)  for(int j = 0 ; j < 2 ; j++)
                res.dp[i][j] = lc.dp[i][1] + rc.dp[1][j];
        }
        return res;
    }
    void Build(int node = 1 , int nl = 1 , int nr = n)
    {
        if(nr - nl == 1)
        {
            t[node].dp[1][1] = abs(d[nl]);
            return;
        }
        int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
        Build(lc , nl , mid);  Build(rc , mid , nr);
        t[node] = Merge(t[lc] , t[rc] , mid);
    }
    void Update(int id , int node = 1 , int nl = 1 , int nr = n)
    {
        if(nr - nl == 1)
        {
            t[node].dp[1][1] = abs(d[nl]);
            return;
        }
        int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
        if(id < mid)
            Update(id , lc , nl , mid);
        else
            Update(id , rc , mid , nr);
        t[node] = Merge(t[lc] , t[rc] , mid);
    }
} seg;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    cin >> n >> q;
    for(int i = 0 ; i < n ; i++)
        cin >> a[i];
    for(int i = 1 ; i < n ; i++)
        d[i] = a[i] - a[i - 1];
    seg.Build();
    for(int i = 0 ; i < q ; i++)
    {
        int l , r , x;  cin >> l >> r >> x;  l--;
        if(l != 0)
        {
            d[l] += x;
            seg.Update(l);
        }
        if(r != n)
        {
            d[r] -= x;
            seg.Update(r);
        }
        cout << seg.t[1].dp[1][1] << '\n';
    }
    return 0;
}

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