oj.uz

Submission #1097322

# Submission time Handle Problem Language Result Execution time Memory
1097322 2024-10-06T20:27:54 Z vjudge1 Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 584 ms 17664 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 2 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 2 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 604 KB Output is correct
9 Correct 7 ms 604 KB Output is correct
10 Correct 7 ms 660 KB Output is correct
11 Correct 7 ms 604 KB Output is correct
12 Correct 7 ms 600 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 2 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 604 KB Output is correct
9 Correct 7 ms 604 KB Output is correct
10 Correct 7 ms 660 KB Output is correct
11 Correct 7 ms 604 KB Output is correct
12 Correct 7 ms 600 KB Output is correct
13 Correct 541 ms 13908 KB Output is correct
14 Correct 562 ms 14044 KB Output is correct
15 Correct 551 ms 14164 KB Output is correct
16 Correct 566 ms 17236 KB Output is correct
17 Correct 584 ms 17232 KB Output is correct
18 Correct 540 ms 17664 KB Output is correct