#include <bits/stdc++.h>
#define fs first
#define sc second
#define MASK(i) (1LL << (i))
#define BIT(i,n) (((n) >> (i)) & 1LL)
#define forw(i, f, e, c) for (int (i) = (f); (i) <= (e); (i) += (c))
#define ford(i, e, f, c) for (int (i) = (e); (i) >= (f); (i) -= (c))
#define pf push_front
#define pb push_back
#define N 200005
#define NMOD 2
#define LOG 19
#define name "optmilk"
#define int long long
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef pair <int,int> pp;
const int dx[] = {0,1,0,-1,1,1,-1,-1}, dy[] = {1,0,-1,0,-1,1,1,-1};
const char dir[] = {'R','D','L','U'};
const int mod = 1e9 + 7, base = 307;
const int MOD[] = {(int)1e9 + 2777, (int) 1e9 + 5277, (int) 1e9 + 8277};
const ll oo = 1e16;
int m,n;
struct segmenttree{
int n;
vector <ll> tree,mi,ma,mil,mal,mir,mar,lazy;
segmenttree(int _n = 0){
n = _n;
tree.assign(4*n+5,0);
ma.assign(4*n+5,0);
mi.assign(4*n+5,0);
mal.assign(4*n+5,0);
mil.assign(4*n+5,oo);
mar.assign(4*n+5,0);
mir.assign(4*n+5,oo);
lazy.assign(4*n+5,0);
}
void gom(int gt, int node){
mi[node] += gt;
ma[node] += gt;
mil[node] += gt;
mir[node] += gt;
mal[node] += gt;
mar[node] += gt;
lazy[node] += gt;
}
void pushdown(int l, int r, int node){
gom(lazy[node],node*2);
gom(lazy[node],node*2+1);
lazy[node] = 0;
}
void update(int l, int r, int x, int y, int gt, int node){
if (l > y || r < x || r < l)return;
if (l >= x && r <= y){
gom(gt,node);
return;
}
pushdown(l,r,node);
int mid = (l + r) >> 1;
update(l,mid,x,y,gt,node*2); update(mid + 1,r,x,y,gt,node*2+1);
mi[node] = min(mi[node*2],mi[node*2+1]);
ma[node] = max(ma[node*2],ma[node*2+1]);
mal[node] = max(ma[node*2],mal[node*2+1]);
mil[node] = min(mi[node*2],mil[node*2+1]);
mar[node] = mar[node*2+1]; mir[node] = mir[node*2+1];
tree[node] = mal[node] - mil[node] + mar[node] - mir[node];
//if (node == 2)cout << tree[2] << endl;
if (ma[node*2] - mi[node*2] + ma[node*2+1] - mi[node*2+1] >= tree[node]){
tree[node] = ma[node*2] - mi[node*2] + ma[node*2+1] - mi[node*2+1];
mal[node] = ma[node*2]; mar[node] = ma[node*2+1];
mil[node] = mi[node*2]; mir[node] = mi[node*2+1];
}
if (mal[node*2] - mil[node*2] + max(mar[node*2],ma[node*2+1]) - min(mir[node*2],mi[node*2+1]) > tree[node]){
mal[node] = mal[node*2]; mil[node] = mil[node*2];
mar[node] = max(mar[node*2],ma[node*2+1]);
mir[node] = min(mir[node*2],mi[node*2+1]);
tree[node] = mal[node] - mil[node] + mar[node] - mir[node];
}
}
void update(int x, int y, int gt){
update(1,n,x,y,gt,1);
}
};
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef CODENE
freopen("a.inp","r",stdin); freopen("a.out","w",stdout);
#else
//freopen(name".in","r",stdin); freopen(name".out","w",stdout);
#endif
cin >> n >> m;
segmenttree it(n);
forw(i,1,n,1){int x; cin >> x; it.update(i,i,x);}
while (m--){
int x,y,gt; cin >> x >> y >> gt;
it.update(x,y,gt);
//cout << it.tree[2] << endl;
cout << max(it.tree[1],it.ma[1] - it.mi[1]) << '\n';
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define forw(i, f, e, c) for (int (i) = (f); (i) <= (e); (i) += (c))
| ^
Main.cpp:112:5: note: in expansion of macro 'forw'
112 | forw(i,1,n,1){int x; cin >> x; it.update(i,i,x);}
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
