#include<bits/stdc++.h>
using namespace std;
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
using LL = long long;
using LD = long double;
using pii = pair<LL,LL>;
#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
cout << "[";
for (auto it = v.begin(); it != v.end();) {
cout << *it;
if (++it != v.end()) cout << ", ";
}
return cout << "]";
}
const LL INF = 1e16;
struct Info {
array<array<LL, 2>, 2> take;
LL left, right;
Info(LL g) : left((g == 0 ? 0LL : g / abs(g))), right(left) {
this->take[0][0] = 0;
this->take[1][1] = abs(g);
this->take[0][1] = this->take[1][0] = -INF;
}
Info() : Info(0) {
this->take[0][0] = this->take[1][1] = -INF;
}
};
struct Merge {
Info operator()(const Info& a, const Info& b) {
Info res;
F0R (i, 2) F0R(j, 2) {
F0R (k, 2) F0R (z, 2) if (a.take[i][k] < INF && b.take[z][j] < INF) {
if (k && z) if (a.right * b.left < 0)
continue;
res.take[i][j] = max(res.take[i][j],
a.take[i][k] + b.take[z][j]
);
}
}
res.left = a.left;
res.right = b.right;
return res;
}
};
template<typename T, typename Merge = plus<T>>
struct seg {
int n;
vector<T> tr;
Merge merge;
seg(int n) : n(n), merge(Merge()), tr((n << 2) + 5, T(0)) {};
seg(vector<LL> a) : seg((int)a.size()) {
function<void (int, int, int)> build = [&](int z, int l, int r) {
if (l == r) {
tr[z] = T(a[l]);
return;
}
int mid = (l + r) >> 1;
build(2 * z, l, mid);
build(2 * z + 1, mid + 1, r);
tr[z] = merge(tr[2 * z], tr[2 * z + 1]);
};
build(1, 0, n - 1);
}
void upd(int z, int l, int r, int qg, LL val) {
if (qg == l && qg == r) {
tr[z] = T(val);
return;
}
int mid = (l + r) >> 1;
if (qg <= mid) {
upd(2 * z, l, mid, qg, val);
} else {
upd(2 * z + 1, mid + 1, r, qg, val);
}
tr[z] = merge(tr[2 * z], tr[2 * z + 1]);
};
T query(int z, int l, int r, int ql, int qr) {
if (ql > qr) return T(0);
if (ql == l && qr == r) {
return tr[z];
}
int mid = (l + r) >> 1;
return merge(query(2 * z, l, mid, ql, min(qr, mid)),
query(2 * z + 1, mid + 1, r, max(ql, mid + 1), qr));
};
void upd(int g, LL val) { upd(1, 0, n - 1, g, val); }
T query(int l, int r) { return query(1, 0, n - 1, l, r); }
};
//var
LL T;
void solve() {
LL n, q;
cin >> n >> q;
vector<LL> a(n);
for (auto& u : a)
cin >> u;
vector<LL> d(n - 1);
F0R (i, n - 1) {
d[i] = a[i] - a[i + 1];
}
seg<Info, Merge> tree(d);
while (q--) {
LL l, r, x;
cin >> l >> r >> x;
l--; r--;
if (l) {
d[l - 1] -= x;
tree.upd(l - 1, d[l - 1]);
}
if (r != n - 1) {
d[r] += x;
tree.upd(r, d[r]);
}
debug(d);
LL ans = 0;
F0R (i, 2) F0R(j, 2) ans = max(ans, tree.tr[1].take[i][j]);
cout << ans << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
T = 1;
//cin >> T;
FOR(t, T)
solve();
cout.flush();
return 0;
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) "zzz"
| ^~~~~
Main.cpp:158:3: note: in expansion of macro 'debug'
158 | debug(d);
| ^~~~~
Main.cpp: In instantiation of 'seg<T, Merge>::seg(int) [with T = Info; Merge = Merge]':
Main.cpp:80:39: required from 'seg<T, Merge>::seg(std::vector<long long int>) [with T = Info; Merge = Merge]'
Main.cpp:143:25: required from here
Main.cpp:77:8: warning: 'seg<Info, Merge>::merge' will be initialized after [-Wreorder]
77 | Merge merge;
| ^~~~~
Main.cpp:76:12: warning: 'std::vector<Info, std::allocator<Info> > seg<Info, Merge>::tr' [-Wreorder]
76 | vector<T> tr;
| ^~
Main.cpp:78:2: warning: when initialized here [-Wreorder]
78 | seg(int n) : n(n), merge(Merge()), tr((n << 2) + 5, T(0)) {};
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1104 KB |
Output is correct |
| 8 |
Correct |
6 ms |
980 KB |
Output is correct |
| 9 |
Correct |
6 ms |
980 KB |
Output is correct |
| 10 |
Correct |
6 ms |
980 KB |
Output is correct |
| 11 |
Correct |
6 ms |
980 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1104 KB |
Output is correct |
| 8 |
Correct |
6 ms |
980 KB |
Output is correct |
| 9 |
Correct |
6 ms |
980 KB |
Output is correct |
| 10 |
Correct |
6 ms |
980 KB |
Output is correct |
| 11 |
Correct |
6 ms |
980 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1096 KB |
Output is correct |
| 13 |
Correct |
663 ms |
50212 KB |
Output is correct |
| 14 |
Correct |
666 ms |
50156 KB |
Output is correct |
| 15 |
Correct |
661 ms |
50068 KB |
Output is correct |
| 16 |
Correct |
649 ms |
49964 KB |
Output is correct |
| 17 |
Correct |
666 ms |
49996 KB |
Output is correct |
| 18 |
Correct |
609 ms |
50728 KB |
Output is correct |
