Submission #972348

#	Time	Username	Problem	Language	Result	Execution time	Memory
972348		detroiddh	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	353 ms	30140 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const ll maxn = 2*1e5+3;
const ll mod = 1e9 + 7;

ll a[maxn] , d[maxn] , st[4 * maxn][2][2];

void construct(int si , int l , int r)
{
    if(l == r)
    {
        st[si][0][0] = st[si][1][0] = st[si][0][1] = 0;
        st[si][1][1] = abs(d[l]);
        return;
    }

    int mid = (l + r) / 2;

    construct(si * 2 , l , mid);
    construct(si * 2 + 1 , mid + 1 , r);

    for(int l1 = 0 ; l1 < 2 ; ++l1)
    {
        for(int r1 = 0 ; r1 < 2 ; ++r1)
        {
            for(int l2 = 0 ; l2 < 2 ; ++l2)
            {
                for(int r2 = 0 ; r2 < 2 ; ++r2)
                {
                    if(d[mid] * d[mid + 1] < 0 && (r1 & l2 == 1)) continue;
                    st[si][l1][r2] = max(st[si][l1][r2] , st[si * 2][l1][r1] + st[si * 2 + 1][l2][r2]);
                }
            }
        }
    }
}

void update(int si , int l , int r , int pos)
{
    if(l == r)
    {
        st[si][1][1] = abs(d[l]);
        return;
    }

    int mid = (l + r) / 2;

    if(pos <= mid) update(si * 2 , l , mid , pos);
    else update(si * 2 + 1 , mid + 1 , r , pos);

    for(int i = 0 ; i < 2 ; ++i)
     for(int j = 0 ; j < 2 ; ++j)
      st[si][i][j] = 0;

    for(int l1 = 0 ; l1 < 2 ; ++l1)
    {
        for(int r1 = 0 ; r1 < 2 ; ++r1)
        {
            for(int l2 = 0 ; l2 < 2 ; ++l2)
            {
                for(int r2 = 0 ; r2 < 2 ; ++r2)
                {
                    if(d[mid] * d[mid + 1] < 0 && (r1 & l2 == 1)) continue;
                    st[si][l1][r2] = max(st[si][l1][r2] , st[si * 2][l1][r1] + st[si * 2 + 1][l2][r2]);
                }
            }
        }
    }
}

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   //freopen("","r",stdin);
   //freopen("","w",stdout);

   int n , q;
   cin>>n>>q;

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

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

   construct(1 , 1 , n - 1);

   ll l , r , x;
   while(q--)
   {
       cin>>l>>r>>x;
       d[l - 1] += x;
       if(l > 1) update(1 , 1 , n - 1 , l - 1);
       d[r] -= x;
       update(1 , 1 , n - 1 , r);

//       if(q == 1)
//       for(int i = 1 ; i <= 4 * n ; ++i)
//        cout<<st[i][0][0]<<" "<<st[i][0][1]<<" "<<st[i][1][0]<<" "<<st[i][1][1]<<'\n';

       cout<<max({st[1][0][0] , st[1][0][1] , st[1][1][0] , st[1][1][1]})<<'\n';
   }
}

Compilation message (stderr)

Main.cpp: In function 'void construct(int, int, int)':
Main.cpp:33:60: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   33 |                     if(d[mid] * d[mid + 1] < 0 && (r1 & l2 == 1)) continue;
      |                                                         ~~~^~~~
Main.cpp: In function 'void update(int, int, int, int)':
Main.cpp:66:60: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   66 |                     if(d[mid] * d[mid + 1] < 0 && (r1 & l2 == 1)) continue;
      |                                                         ~~~^~~~

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