#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF 1e17
#define zero (int)0
#define MX (int)3e5+5
#define LMX (int)1e6
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
const int mod = 1e9+7; //may change to that 99.. number.
struct node
{
int st[3][3];
node(int get = -INF)
{
for(int i = 0; i <= 2; i++)
{
for(int j = 0; j <= 2; j++)
st[i][j] = -INF;
}
if(get == -INF)
return;
st[0][1] = st[1][0] = get;
st[1][1] = 0;
st[1][2] = st[2][1] = -get;
return;
}
};
node merge(node n1, node n2)
{
node n3;
for(int i = 0; i <= 2; i++)
{
for(int j = 0; j <= 2; j++)
{
for(int k = 0; k <= 2; k++)
{
int optmilk = n1.st[i][2-k]+n2.st[k][j];
n3.st[i][j] = max(n3.st[i][j], optmilk);
}
}
}
return n3;
}
int extract(node n)
{
return n.st[1][1];
}
struct segment_tree
{
vector<node> tree;
vector<int> delta;
void init()
{
tree.resize(LMX);
delta.resize(LMX);
}
void paint(int x, int id)
{
for(int i = 0; i <= 2; i++)
{
for(int j = 0; j <= 2; j++)
tree[id].st[i][j]-=(i+j-2)*x;
}
return;
}
void push(int id)
{
delta[2*id]+=delta[id];
delta[2*id+1]+=delta[id];
paint(delta[id], 2*id);
paint(delta[id], 2*id+1);
delta[id] = 0;
return;
}
void build(const vector<int> &a, int id, int l, int r)
{
int m = (l+r)/2;
if(l == r)
{
tree[id] = node(a[m]);
return;
}
build(a, 2*id, l, m);
build(a, 2*id+1, m+1, r);
tree[id] = merge(tree[2*id], tree[2*id+1]);
return;
}
void upd(int ql, int qr, int X, int id, int l, int r)
{
int m = (l+r)/2;
if(ql <= l && r <= qr)
{
paint(X, id);
delta[id]+=X;
return;
}
if(qr < l || r < ql)
return;
push(id);
upd(ql, qr, X, 2*id, l, m);
upd(ql, qr, X, 2*id+1, m+1, r);
tree[id] = merge(tree[2*id], tree[2*id+1]);
return;
}
};
signed main()
{
fast();
segment_tree work;
work.init();
int n, q;
cin >> n >> q;
vector<int> a(n+1);
for(int i = 1; i <= n; i++)
cin >> a[i];
work.build(a, 1, 1, n);
while(q--)
{
int l, r, x;
cin >> l >> r >> x;
work.upd(l, r, x, 1, 1, n);
cout << extract(work.tree[1]) << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
78592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
78592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
78592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
