Submission #465752

#TimeUsernameProblemLanguageResultExecution timeMemory
465752JovanBSjeckanje (COCI21_sjeckanje)C++17
110 / 110
393 ms29596 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int N = 200000; struct Segment{ ll mat[2][2]; } seg[4*N+5]; ll niz[N+5]; ll b[N+5]; void mrg(int node){ for(int i=0; i<2; i++) for(int j=0; j<2; j++) seg[node].mat[i][j] = 0; for(int i=0; i<2; i++) for(int j=0; j<2; j++) for(int k=0; k<2; k++) seg[node].mat[i][j] = max(seg[node].mat[i][j], seg[node*2].mat[i][k] + seg[node*2+1].mat[k][j]); } void init(int node, int l, int r){ if(l == r){ seg[node].mat[0][0] = max(niz[l], 0LL); seg[node].mat[1][1] = max(-niz[l], 0LL); return; } int mid = (l+r)/2; init(node*2, l, mid); init(node*2+1, mid+1, r); mrg(node); } void upd(int node, int l, int r, int x){ if(l == r){ seg[node].mat[0][0] = max(niz[l], 0LL); seg[node].mat[1][1] = max(-niz[l], 0LL); return; } int mid = (l+r)/2; if(x <= mid) upd(node*2, l, mid, x); else upd(node*2+1, mid+1, r, x); mrg(node); } int main(){ ios_base::sync_with_stdio(false), cin.tie(0); cout.precision(10); cout << fixed; int n, qrs; cin >> n >> qrs; for(int i=1; i<=n; i++) cin >> b[i]; for(int i=1; i<n; i++) niz[i] = b[i+1] - b[i]; init(1, 1, n-1); while(qrs--){ int l, r, x; cin >> l >> r >> x; if(l > 1){ niz[l-1] += x; upd(1, 1, n-1, l-1); } if(r < n){ niz[r] -= x; upd(1, 1, n-1, r); } cout << max(max(max(seg[1].mat[1][1], seg[1].mat[1][0]), seg[1].mat[0][0]), seg[1].mat[0][1]) << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...