//@timothyg
#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
return os << '{' << p.first << ", " << p.second << '}';
}
template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &os, const T &c) {
os << '[';
for (auto it = c.begin(); it != c.end(); ++it)
os << &", "[2 * (it == c.begin())] << *it;
return os << ']';
}
#define _NTH_ARG(_1, _2, _3, _4, _5, _6, N, ...) N
#define _FE_0(_CALL, ...)
#define _FE_1(_CALL, x) _CALL(x)
#define _FE_2(_CALL, x, ...) _CALL(x) _FE_1(_CALL, __VA_ARGS__)
#define _FE_3(_CALL, x, ...) _CALL(x) _FE_2(_CALL, __VA_ARGS__)
#define _FE_4(_CALL, x, ...) _CALL(x) _FE_3(_CALL, __VA_ARGS__)
#define _FE_5(_CALL, x, ...) _CALL(x) _FE_4(_CALL, __VA_ARGS__)
#define FOR_EACH_MACRO(MACRO, ...) \
_NTH_ARG(dummy, ##__VA_ARGS__, _FE_5, _FE_4, _FE_3, _FE_2, _FE_1, _FE_0) \
(MACRO, ##__VA_ARGS__)
#define DBG_OUT(x) #x " = " << x << "; "
#define dbg(...) \
cerr << "Line " << __LINE__ << ": " FOR_EACH_MACRO(DBG_OUT, __VA_ARGS__) << '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define vsz(a) (int)a.size()
#define f first
#define s second
struct node{
int isDummy = 0;
ll borders[2] = {0, 0}; //border values of segment
ll dp[2][2] = {{0,0}, {0,0}}; //take/not-take left and right border values
node(){}
node(ll v){
borders[0] = borders[1] = v;
dp[0][1] = dp[1][0] = dp[0][0] = 0;
dp[1][1] = abs(v);
}
//assume current is left
node comb(node& other){
node ret;
ret.borders[0] = borders[0];
ret.borders[1] = other.borders[1];
//[ ][ ]
//l mo r
//m and o same means the taken segments are combined
for(int l = 0; l<2; l++){
for(int m = 0; m < 2; m++){
for(int o = 0; o < 2; o++){
for(int r = 0; r < 2; r++){
if(m && o){
//it's never optimal to take two opposite sign values
if((borders[1] < 0) == (other.borders[0] < 0)){
ret.dp[l][r] = max(ret.dp[l][r], dp[l][m] + other.dp[o][r]);
}
}else{
ret.dp[l][r] = max(ret.dp[l][r], dp[l][m] + other.dp[o][r]);
}
}
}
}
}
return ret;
}
//modify a single-element node range + v
void upd(ll v){
borders[0] += v;
borders[1] += v;
dp[1][1] = abs(borders[0]);
}
};
struct segtree
{
node val;
int gL, gR, mid;
segtree *left, *right;
segtree(int l, int r, vector<node>& nums)
{
gL = l; gR = r; mid = (gL+gR)/2;
if (l == r)
{
val = nums[l];
}
else
{
left = new segtree(l, mid, nums), right = new segtree(mid + 1, r, nums);
val = left->val.comb(right->val);
}
}
node query(int l, int r)
{
if (gL > r || gR < l)
{
node dummy; dummy.isDummy=1;
return dummy;
}
if (gL == l && gR == r)
{
return val;
}
node a = left->query(l, min(r, mid)), b = right->query(max(l, mid + 1), r);
if(a.isDummy) return b;
if(b.isDummy) return a;
return a.comb(b);
}
void update(int idx, ll updval)
{
if (gL == gR)
{
val.upd(updval);
}
else
{
if (idx <= (gL + gR) / 2)
{
left->update(idx, updval);
}
else
{
right->update(idx, updval);
}
val = left->val.comb(right->val);
}
}
};
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int N, Q; cin >> N >> Q;
vector<node> D(N-1);
int a; cin >> a;
//compute difference arrays
for(int i = 0; i<N-1; i++){
int b; cin >> b;
D[i] = node(b - a);
swap(a, b);
}
//a_(i+1) - a(i)
segtree sgt(0, N-2, D);
// for (int j = 0; j < N-1; j++){
// dbg(sgt.query(j, j).borders[0], sgt.query(j, j).borders[1]);
// }
//-2 2 -1
for(int q = 0; q<Q; q++){
int l, r; ll x; cin >> l >> r >> x;
l--, r--;
if(l-1 >= 0){
sgt.update(l-1, x); //a_(i+1) is changed
}
if(r < N-1){
sgt.update(r, -x); //ai is changed
}
// for (int j = 0; j < N-1; j++){
// dbg(sgt.query(j, j).borders[0], sgt.query(j, j).borders[1]);
// }
// cout << endl;
cout << max(
{sgt.val.dp[0][0], sgt.val.dp[0][1], sgt.val.dp[1][0], sgt.val.dp[1][1]}
) << '\n';
}
return 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 |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 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 |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1188 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1100 KB |
Output is correct |
| 9 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1188 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 12 |
Correct |
6 ms |
1100 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 |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1188 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1100 KB |
Output is correct |
| 9 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1188 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 12 |
Correct |
6 ms |
1100 KB |
Output is correct |
| 13 |
Correct |
772 ms |
57984 KB |
Output is correct |
| 14 |
Correct |
738 ms |
58048 KB |
Output is correct |
| 15 |
Correct |
746 ms |
57972 KB |
Output is correct |
| 16 |
Correct |
691 ms |
57844 KB |
Output is correct |
| 17 |
Correct |
709 ms |
57800 KB |
Output is correct |
| 18 |
Correct |
677 ms |
58664 KB |
Output is correct |
