#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int NN = 1e6 + 5;
const int mo = 1e9 + 7;
const ld eps = 1e-9;
ll n, q, a[NN];
ll ST[4 * NN][3][3];
ll MI[4 * NN];
ll MA[4 * NN];
void init(ll aa, ll bb, ll ee)
{
if(aa == bb)
{
MI[ee] = a[aa];
MA[ee] = a[aa];
for(ll i = 0; i < 3; i++)
for(ll j = 0; j < 3; j++)
{
if(i != 2 && j != 2)
ST[ee][i][j] = -1e18;
else
{
ll cst = 0;
if(i == 0)cst -= MI[ee];
if(j == 0)cst -= MI[ee];
if(i == 1)cst += MA[ee];
if(j == 1)cst += MA[ee];
ST[ee][i][j] = cst;
}
}
}
else
{
ll ce = (aa + bb) / 2;
init(aa, ce, ee * 2);
init(ce + 1, bb, ee * 2 + 1);
MI[ee] = min(MI[ee * 2], MI[ee * 2 + 1]);
MA[ee] = max(MA[ee * 2], MA[ee * 2 + 1]);
for(ll i = 0; i < 3; i++)
for(ll j = 0; j < 3; j++)
{
if(i != 2 && j != 2)
ST[ee][i][j] = -1e18;
else
{
ll cst = 0;
if(i == 0)cst -= MI[ee];
if(j == 0)cst -= MI[ee];
if(i == 1)cst += MA[ee];
if(j == 1)cst += MA[ee];
ST[ee][i][j] = cst;
}
}
for(ll i = 0; i < 3; i++)
for(ll j = 0; j < 3; j++)
{
ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2][i][j]);
ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2 + 1][i][j]);
ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2][i][0] + ST[ee * 2 + 1][1][j]);
ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2][i][1] + ST[ee * 2 + 1][0][j]);
ST[ee][i][j] = max(ST[ee][i][j], ST[ee * 2][i][2] + ST[ee * 2 + 1][2][j]);
}
}
// for(ll i = 0; i < 3; i++)
// for(ll j = 0; j < 3; j++)
// cout << aa << " " << bb << " " << i << "(---)" << j << " = " << ST[ee][i][j] << "\n";
}
ll d[3030][4];
ll depe(ll pos, ll tr)
{
if(pos > n && tr == 0)
return 0;
if(pos > n)
return -1e18;
ll &ret = d[pos][tr];
if(ret == -1)
{
ret = depe(pos + 1, tr);
if(tr == 0)
{
ret = max(ret, depe(pos + 1, 1) + a[pos]);
ret = max(ret, depe(pos + 1, 2) - a[pos]);
}
else
if(tr == 1)
ret = max(ret, depe(pos + 1, 0) - a[pos]);
else
ret = max(ret, depe(pos + 1, 0) + a[pos]);
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> q;
// while(1)
{
for(ll i = 1; i <= n; i++)
{
// a[i] = rand() % 10;
cin >> a[i];
// cout << a[i] << " ";
}
// cout << "\n";
init(1, n, 1);
for(ll i = 1; i <= q; i++)
{
ll L, R, tam;
cin >> L >> R >> tam;
for(ll i = L; i <= R; i++)
a[i] += tam;
init(1, n, 1);
// memset(d, -1, sizeof(d));
// cout << ST[1][2][2] << " " << depe(1, 0) << "\n";
// if(ST[1][2][2] != depe(1, 0))
// {
// return 0;
// }
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
