#include <bits/stdc++.h>
#define int long long
#define pi pair<int,int>
#define pb push_back
#define V vector
#define vi V<int>
#define mi map<int,int>
#define MOD 1000000007
#define MOD2 998244353
#define mp make_pair
#define ins insert
#define qi queue<int>
#define pqi priority_queue<int>
#define si set<int>
#define v2i V<vi>
#define v3i V<v2i>
#define v4i V<v3i>
#define v5i V<v4i>
#define INF 1e18
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl "\n"
#define lb lower_bound
#define ub upper_bound
#define print(x) cout << x<<" ";
#define vpi V<pi>
#define Y cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define msi multiset<int>
#define F first
#define S second
#define ld long double
#define RE return;
#define IMP cout<<-1<<endl;return;
using namespace std;
template <typename T>
std::istream& operator>>(std::istream& in, std::vector<T>& vec) {
for (T& x : vec) {
in >> x;
}
return in;
}
struct Node{
int left=-1; int right=-1;
int val=0;
int misr = 0; int misl = 0; int missb = 0;
};
vector<int> diff;
V<Node> seg;
Node merge(Node a, Node b){
Node n; n.left = a.left; n.right = b.right;
if(a.right==b.left){
n.val = a.val + b.val;
n.misr = a.val + b.misr;
n.misl = a.misl+ b.val;
n.missb = a.misl + b.misr;
}else{
n.val = max(a.val + b.misl, a.misr + b.val);
n.misr = max(a.val + b.missb, a.misr + b.misr);
n.misl = max(a.missb+b.val, a.misl + b.misl);
n.missb = max(a.missb + b.misr, a.misl + b.missb);
}
return n;
};
void build(int node, int l, int r){
if(l==r){
Node ne; ne.left = ne.right = (diff[l]>=0);
ne.val = abs(diff[l]);
seg[node] = ne;
return;
}
int mid = (l+r)/2;
build(2*node, l, mid); build(2*node+1, mid+1, r);
seg[node] = merge(seg[2*node], seg[2*node+1]);
}
void update(int node, int l, int r, int i){
if(l==r){
Node ne; ne.left = ne.right = (diff[l]>=0);
ne.val = abs(diff[l]);
seg[node] = ne;
return;
}
int mid = (l+r)/2;
if(i<=mid)update(2*node, l, mid,i);
else update(2*node+1, mid+1, r,i);
seg[node] = merge(seg[2*node], seg[2*node+1]);
}
signed main(){
fastio;
int n,q; cin >> n>>q; seg.resize(2*n);
vi a(n); cin >> a; for(int i=0; i<n-1; i++) diff.pb(a[i+1]-a[i]);
build(1,0,n-2);
while(q--){
int l, r,v; cin >>l>>r>>v;
if(l>1) diff[l-2] += v, update(1,0,n-2,l-2);
if(r<n) diff[r-1] -=v, update(1, 0, n-2, r-1);
cout << seg[1].val<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
