#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
#define eprintf(...) 42
#endif
//order statistic tree
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<
T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update
>;
#define pb push_back
#define mp make_pair
#define ins insert
#define popb pop_back
#define popf pop_front
#define ft front
#define bk back
#define fr first
#define sc second
using ll = long long;
using ld = long double;
using db = double;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<ld,ld>;
using str = string;
const int NAX = (int)1000000;
const int MOD = (int)998244353;
template<int MOD, int RT> struct mint {
static const int mod = MOD;
static constexpr mint rt() { return RT; } // primitive root for FFT
int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
mint():v(0) {}
mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
if (v < 0) v += MOD; }
bool operator==(const mint& o) const {
return v == o.v; }
friend bool operator!=(const mint& a, const mint& b) {
return !(a == b); }
friend bool operator<(const mint& a, const mint& b) {
return a.v < b.v; }
mint& operator+=(const mint& o) {
if ((v += o.v) >= MOD) v -= MOD;
return *this; }
mint& operator-=(const mint& o) {
if ((v -= o.v) < 0) v += MOD;
return *this; }
mint& operator*=(const mint& o) {
v = int((ll)v*o.v%MOD); return *this; }
mint& operator/=(const mint& o) { return (*this) *= inv(o); }
friend mint pow(mint a, ll p) {
mint ans = 1; assert(p >= 0);
for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans; }
friend mint inv(const mint& a) { assert(a.v != 0);
return pow(a,MOD-2); }
mint operator-() const { return mint(-v); }
mint& operator++() { return *this += 1; }
mint& operator--() { return *this -= 1; }
friend mint operator+(mint a, const mint& b) { return a += b; }
friend mint operator-(mint a, const mint& b) { return a -= b; }
friend mint operator*(mint a, const mint& b) { return a *= b; }
friend mint operator/(mint a, const mint& b) { return a /= b; }
};
using mi = mint<MOD,5>;
using vmi = vector<mi>;
using pmi = pair<mi,mi>;
using vpmi = vector<pmi>;
ll n, q;
ll D[300000];
struct Node{
ll borders[2];
ll dp[2][2];
Node(){}
Node(ll v){
borders[1] = borders[0] = v;
memset(dp, 0, sizeof(dp));
dp[1][1] = abs(v);
}
Node Merge(Node right){
Node res;
res.borders[0] = borders[0], res.borders[1] = right.borders[1];
memset(res.dp, 0, sizeof(res.dp));
for (int a = 0; a < 2; a++){
for (int b = 0; b < 2; b++){
for (int c = 0; c < 2; c++){
for (int d = 0; d < 2; d++){
if (c && b){
//this implies that we merge the two segments because we include [l..r] ->[l...r2]
if ((borders[1] < 0) == (right.borders[0] < 0)){
//check signs, dumb to use two same signed borders because we have more optimal arrangement
res.dp[a][d] = max(res.dp[a][d], dp[a][b] + right.dp[c][d]);
}
}else{
//we do not merge them => they are seperate segments
res.dp[a][d] = max(res.dp[a][d], dp[a][b] + right.dp[c][d]);
}
}
}
}
}
return res;
}
void upd(ll u){
borders[1]+=u;
borders[0]+=u;
dp[1][1]=abs(u);
}
};
template<class V, int NV> class SegmentTree{
public:
Node t[NV * 3];
void build(int l = 0, int r = n - 2, int node = 1){
if (l ==r){
t[node] = Node(D[l]);
return;
}
int mid = (l + r)/2;
build(l, mid, node * 2);
build(mid + 1, r, node * 2 + 1);
t[node] = t[node * 2].Merge(t[node * 2 + 1]);
}
void update(int l = 0, int r = n - 2, int node = 1, int pos = 1, ll updval = 0){
if (l == r){
t[node] = Node(D[l]);
return;
}
int mid = (l + r)/2;
if (pos <= mid)update(l,mid,node*2,pos, updval);
else update(mid+1,r,node*2+1,pos, updval);
t[node] = t[node * 2].Merge(t[node * 2 + 1]);
}
};
SegmentTree<int,1<<20>st;
void Task_Sjeckanje(){
cin >> n >> q;
vector<ll>a(n);
memset(D, 0, sizeof(D));
for (int i = 0; i<n; i++){
cin >> a[i];
if (i)D[i - 1] = a[i] - a[i - 1];
}
st.build(0,n-2,1);
while(q--){
ll b,c, d;
cin >> b >> c >> d;
--b;
--c;
if (b){
D[b-1]+=d;
st.update(0,n-2,1,b-1, d);
}
if(c < n - 1){
D[c]-=d;
st.update(0,n-2,1,c, -d);
}
//st.build();
ll ans = 0;
for(int i = 0; i < 2; i++){
for (int j =0 ; j < 2; j++){
ans = max(ans, st.t[1].dp[i][j]);
}
}
cout<<ans<<endl;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("optmilk.in", "r", stdin);
//freopen("optmilk.out", "w", stdout);
Task_Sjeckanje();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2632 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2640 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2632 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2640 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
11 ms |
3176 KB |
Output is correct |
| 8 |
Correct |
10 ms |
3160 KB |
Output is correct |
| 9 |
Correct |
10 ms |
3156 KB |
Output is correct |
| 10 |
Correct |
10 ms |
3172 KB |
Output is correct |
| 11 |
Correct |
10 ms |
3200 KB |
Output is correct |
| 12 |
Correct |
10 ms |
3156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2632 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2640 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
11 ms |
3176 KB |
Output is correct |
| 8 |
Correct |
10 ms |
3160 KB |
Output is correct |
| 9 |
Correct |
10 ms |
3156 KB |
Output is correct |
| 10 |
Correct |
10 ms |
3172 KB |
Output is correct |
| 11 |
Correct |
10 ms |
3200 KB |
Output is correct |
| 12 |
Correct |
10 ms |
3156 KB |
Output is correct |
| 13 |
Correct |
875 ms |
38020 KB |
Output is correct |
| 14 |
Correct |
880 ms |
37916 KB |
Output is correct |
| 15 |
Correct |
875 ms |
37904 KB |
Output is correct |
| 16 |
Correct |
897 ms |
38004 KB |
Output is correct |
| 17 |
Correct |
894 ms |
37820 KB |
Output is correct |
| 18 |
Correct |
829 ms |
38532 KB |
Output is correct |
