oj.uz

Submission #1097321

# Submission time Handle Problem Language Result Execution time Memory
1097321 2024-10-06T20:27:03 Z Sam_arvandi Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 558 ms 20816 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define mp make_pair


const int mn = 2e5 + 5, mn2 = (1<<18) + 5;
ll d[mn2];
int a[mn];
bool c[mn];
ll dp[mn2*2][2][2];

void make(int id, int L, int R)
{
     int mid = (L+R)/2;
     if (L+2 == R)
     {
	  dp[id][0][0] = 0;
	  dp[id][0][1] = max((ll)(0), d[L+1]);
	  dp[id][1][0] = max((ll)(0), d[L]);
	  if (c[L] == c[L+1]) dp[id][1][1] = max((ll)(0), d[L]) + max((ll)(0), d[L+1]);
	  else dp[id][1][1] = max(dp[id][1][0], dp[id][0][1]);
	  return;
     }
     make(id*2, L, mid);
     make(id*2 + 1, mid, R);
     for (int i = 0; i<= 1; i++)
     {
	  for (int j = 0; j<= 1; j++)
	  {
	       if (c[mid] == c[mid-1]) dp[id][i][j] = dp[id*2][i][1] + dp[id*2 + 1][1][j];
	       else dp[id][i][j] = max(dp[id*2][i][0]+dp[id*2 + 1][1][j], dp[id*2][i][1]+dp[id*2 + 1][0][j]);
	  }
     }
     return;
}


void update(int id, int L ,int R, int ind, ll x, bool col)
{
     int mid = (L+R)/2;
     if (L+2 == R)
     {
	  d[ind] = x;
	  c[ind] = col;
	  dp[id][0][0] = 0;
	  dp[id][0][1] = max((ll)(0), d[L+1]);
	  dp[id][1][0] = max((ll)(0), d[L]);
	  if (c[L] == c[L+1]) dp[id][1][1] = max((ll)(0), d[L]) + max((ll)(0), d[L+1]);
	  else dp[id][1][1] = max(dp[id][1][0], dp[id][0][1]);
	  return;
     }
     if (ind >= mid) update(id*2 + 1, mid, R, ind, x, col);
     else update(id*2 , L, mid, ind, x, col);

     for (int i = 0; i<= 1; i++)
     {
	  for (int j = 0; j<= 1; j++)
	  {
	       if (c[mid] == c[mid-1]) dp[id][i][j] = dp[id*2][i][1] + dp[id*2 + 1][1][j];
	       else dp[id][i][j] = max(dp[id*2][i][0]+dp[id*2 + 1][1][j], dp[id*2][i][1]+dp[id*2 + 1][0][j]);
	  }
     }
     return;
}


int main()
{
     int n, q, l, r, n2 = 1;
     ll x;
     cin >> n >> q;
     while (n2 < n) n2 *= 2;
     for (int i = 1; i<= n; i++) cin >> a[i];
     for (int i = 2; i<= n; i++)
     {
	  if (a[i] >= a[i-1])
	  {
	       c[i-1] = 0;
	       d[i-1] = a[i] - a[i-1];
	  }
	  else
	  {
	       c[i-1] = 1;
	       d[i-1] = a[i-1] - a[i];
	  }
     }
     make(1, 1, n2+1);
     for (int i  = 1; i<= q; i++)
     {
	  cin >> l >> r >> x;
	  if (x >= 0)
	  {
	       if (l>1)
	       {
		    if (c[l-1])
		    {
			 if (x >= d[l-1])
			 {
			      update(1, 1, n2+1, l-1, x-d[l-1], 0);
			 }
			 else update(1, 1, n2+1, l-1, d[l-1]-x, 1);
		    }
		    else
		    {
			 update(1, 1, n2+1, l-1, x+d[l-1], 0);
		    }
	       }
	       if (r < n)
	       {
		    if (c[r])
		    {
			 update(1, 1, n2+1, r, x+d[r], 1);
		    }
		    else
		    {
			 if (x > d[r])
			 {
			      update(1, 1, n2+1, r, x-d[r], 1);
			 }
			 else update(1, 1, n2+1, r, d[r]-x, 0);
		    }
	       }
	  }
	  else
	  {
	       x = -x;
	       if (l > 1)
	       {
		    if (c[l-1])
		    {
			 update(1, 1, n2+1, l-1, x+d[l-1], 1);
		    }
		    else
		    {
			 if (x > d[l-1])
			 {
			      update(1, 1, n2+1, l-1, x-d[l-1], 1);
			 }
			 else update(1, 1, n2+1, l-1, d[l-1]-x, 0);
		    }
	       }
	       if (r < n)
	       {
		    if (c[r])
		    {
			 if (x >= d[r])
			 {
			      update(1, 1, n2+1, r, x-d[r], 0);
			 }
			 else update(1, 1, n2+1, r, d[r]-x, 1);
		    }
		    else
		    {
			 update(1, 1, n2+1, r, d[r]+x, 0);
		    }
	       }
	  }
	  cout << dp[1][1][1] << "\n";
     }
     return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 7 ms 604 KB Output is correct
8 Correct 7 ms 732 KB Output is correct
9 Correct 8 ms 536 KB Output is correct
10 Correct 7 ms 600 KB Output is correct
11 Correct 7 ms 604 KB Output is correct
12 Correct 7 ms 604 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 7 ms 604 KB Output is correct
8 Correct 7 ms 732 KB Output is correct
9 Correct 8 ms 536 KB Output is correct
10 Correct 7 ms 600 KB Output is correct
11 Correct 7 ms 604 KB Output is correct
12 Correct 7 ms 604 KB Output is correct
13 Correct 540 ms 20304 KB Output is correct
14 Correct 558 ms 20312 KB Output is correct
15 Correct 545 ms 20208 KB Output is correct
16 Correct 556 ms 20052 KB Output is correct
17 Correct 553 ms 20052 KB Output is correct
18 Correct 546 ms 20816 KB Output is correct