#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;
cout << 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, d[r]-x, 0);
}
else update(1, 1, n2+1, r, x-d[r], 1);
}
else
{
update(1, 1, n2+1, r, d[r]+x, 0);
}
}
}
cout << dp[1][1][1] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
