Submission #1097322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097322		vjudge1	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	584 ms	17664 KiB

Main

#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 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55