oj.uz

Submission #972348

# Submission time Handle Problem Language Result Execution time Memory
972348 2024-04-30T11:22:40 Z detroiddh Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 353 ms 30140 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 4 ms 4700 KB Output is correct
8 Correct 4 ms 4700 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 6 ms 4956 KB Output is correct
11 Correct 4 ms 4652 KB Output is correct
12 Correct 4 ms 4836 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 4 ms 4700 KB Output is correct
8 Correct 4 ms 4700 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 6 ms 4956 KB Output is correct
11 Correct 4 ms 4652 KB Output is correct
12 Correct 4 ms 4836 KB Output is correct
13 Correct 342 ms 29556 KB Output is correct
14 Correct 342 ms 29468 KB Output is correct
15 Correct 353 ms 29432 KB Output is correct
16 Correct 338 ms 29264 KB Output is correct
17 Correct 333 ms 29164 KB Output is correct
18 Correct 291 ms 30140 KB Output is correct