#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.hpp"
#endif
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define rep(i, N) for (int i = 0; i < (N); ++i)
#define rrep(i, N) for (int i = (N)-1; i >= 0; --i)
#define rep1(i, N) for (int i = 1; i <= (N); ++i)
#define rep2(i, s, e) for (int i = (s); i <= (e); ++i)
#ifdef DEBUG
#define debug(x...) \
do { \
++dbg::depth; \
string dbg_vals = dbg::to_string(x); \
--dbg::depth; \
dbg::fprint(__func__, __LINE__, #x, dbg_vals); \
} while (false)
#else
#define debug(...) 42
#endif
template<typename T> inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }
template<typename T> inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }
constexpr long long INF{1LL << 50};
template<typename T> class segment_tree {
private:
int n;
vector<T> a;
public:
segment_tree(int n_): n{n_}, a(n << 1) {}
segment_tree(const vector<T>& b): n{int(b.size())}, a(n << 1) {
for (int i{}; i < n; ++i) a[i + n] = b[i];
for (int i{n - 1}; i > 0; --i) a[i] = a[i << 1] + a[i << 1 | 1];
debug(a);
}
void update(int i, const T& v) {
a[i += n] = v;
for (i >>= 1; i > 0; i >>= 1) a[i] = a[i << 1] + a[i << 1 | 1];
}
T query(int s, int e) const {
debug(a);
T f{}, b{};
for (s += n, e += n; s < e; s >>= 1, e >>= 1) {
if (s & 1) f = f + a[s++];
if (e & 1) b = a[--e] + b;
}
debug(f, b);
return f + b;
}
};
struct node {
bool e;
long long f{}, l{};
array<long long, 4> a{};
node() { e = true; }
node(long long v) {
e = false;
f = l = v;
a[0b00] = 0;
a[0b01] = -INF;
a[0b10] = -INF;
a[0b11] = abs(v);
}
friend node operator+(const node& x, const node& y) {
if (x.e) return y;
if (y.e) return x;
node r;
r.f = x.f, r.l = y.l;
r.e = false;
if ((x.l <= 0 && y.f <= 0) || (x.l >= 0 && y.f >= 0)) {
r.a[0b00] = max(x.a[0b00], x.a[0b01]) + max(y.a[0b00], y.a[0b10]);
r.a[0b01] = max(x.a[0b00], x.a[0b01]) + max(y.a[0b01], y.a[0b11]);
r.a[0b10] = max(x.a[0b10], x.a[0b11]) + max(y.a[0b00], y.a[0b10]);
r.a[0b11] = max(x.a[0b10], x.a[0b11]) + max(y.a[0b01], y.a[0b11]);
} else {
r.a[0b00] = max(x.a[0b00] + max(y.a[0b00], y.a[0b10]),
x.a[0b01] + y.a[0b00]);
r.a[0b01] = max(x.a[0b00] + max(y.a[0b01], y.a[0b11]),
x.a[0b01] + y.a[0b01]);
r.a[0b10] = max(x.a[0b10] + max(y.a[0b00], y.a[0b10]),
x.a[0b11] + y.a[0b00]);
r.a[0b11] = max(x.a[0b10] + max(y.a[0b01], y.a[0b11]),
x.a[0b11] + y.a[0b01]);
}
rep(i, 4) if (r.a[i] < 0) r.a[i] = -INF;
return r;
}
#ifdef DEBUG
friend string to_string(const node& x) { return dbg::to_string(x.a); }
#endif
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<long long> a(n);
rep(i, n) cin >> a[i];
adjacent_difference(all(a), a.begin());
a[0] = 0;
vector<node> b(n);
rep(i, n) b[i] = node(a[i]);
segment_tree<node> seg(b);
rep(_, q) {
int l, r;
long long x;
cin >> l >> r >> x;
--l;
a[l] += x;
seg.update(l, node(a[l]));
if (r < n) {
a[r] -= x;
seg.update(r, node(a[r]));
}
node k{seg.query(0, n)};
debug(a, k.a);
cout << max(k.a[0], k.a[1]) << '\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:25:24: warning: statement has no effect [-Wunused-value]
25 | #define debug(...) 42
| ^~
Main.cpp:142:9: note: in expansion of macro 'debug'
142 | debug(a, k.a);
| ^~~~~
Main.cpp: In instantiation of 'segment_tree<T>::segment_tree(const std::vector<_Tp>&) [with T = node]':
Main.cpp:125:29: required from here
Main.cpp:25:24: warning: statement has no effect [-Wunused-value]
25 | #define debug(...) 42
| ^~
Main.cpp:44:9: note: in expansion of macro 'debug'
44 | debug(a);
| ^~~~~
Main.cpp: In instantiation of 'T segment_tree<T>::query(int, int) const [with T = node]':
Main.cpp:141:30: required from here
Main.cpp:25:24: warning: statement has no effect [-Wunused-value]
25 | #define debug(...) 42
| ^~
Main.cpp:53:9: note: in expansion of macro 'debug'
53 | debug(a);
| ^~~~~
Main.cpp:25:24: warning: statement has no effect [-Wunused-value]
25 | #define debug(...) 42
| ^~
Main.cpp:59:9: note: in expansion of macro 'debug'
59 | debug(f, b);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
316 KB |
Output is correct |
| 2 |
Correct |
1 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
316 KB |
Output is correct |
| 2 |
Correct |
1 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
5 ms |
848 KB |
Output is correct |
| 8 |
Correct |
5 ms |
848 KB |
Output is correct |
| 9 |
Correct |
5 ms |
976 KB |
Output is correct |
| 10 |
Correct |
7 ms |
976 KB |
Output is correct |
| 11 |
Correct |
5 ms |
964 KB |
Output is correct |
| 12 |
Correct |
5 ms |
976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
316 KB |
Output is correct |
| 2 |
Correct |
1 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
5 ms |
848 KB |
Output is correct |
| 8 |
Correct |
5 ms |
848 KB |
Output is correct |
| 9 |
Correct |
5 ms |
976 KB |
Output is correct |
| 10 |
Correct |
7 ms |
976 KB |
Output is correct |
| 11 |
Correct |
5 ms |
964 KB |
Output is correct |
| 12 |
Correct |
5 ms |
976 KB |
Output is correct |
| 13 |
Correct |
556 ms |
43896 KB |
Output is correct |
| 14 |
Correct |
534 ms |
43896 KB |
Output is correct |
| 15 |
Correct |
542 ms |
43888 KB |
Output is correct |
| 16 |
Correct |
509 ms |
43720 KB |
Output is correct |
| 17 |
Correct |
522 ms |
43712 KB |
Output is correct |
| 18 |
Correct |
546 ms |
44624 KB |
Output is correct |
