제출 #1032044

#제출 시각아이디문제언어결과실행 시간메모리
1032044BF001Sjeckanje (COCI21_sjeckanje)C++17
110 / 110
574 ms47696 KiB
#include<bits/stdc++.h> using namespace std; #define N 200005 #define int long long struct node{ int b[2]; int dp[2][2]; node(){ for (int i = 0; i <= 1; i++){ for (int j = 0; j <= 1; j++){ dp[i][j] = b[i] = 0; } } } node operator + (node o){ node rt; rt.b[0] = b[0]; rt.b[1] = o.b[1]; for (int l = 0; l <= 1; l++){ for (int r = 0; r <= 1; r++){ for (int mi1 = 0; mi1 <= 1; mi1++){ for (int mi2 = 0; mi2 <= 1; mi2++){ if (mi1 && mi2){ if (b[1] * o.b[0] > 0){ rt.dp[l][r] = max(rt.dp[l][r], dp[l][mi1] + o.dp[mi2][r]); } } else{ rt.dp[l][r] = max(rt.dp[l][r], dp[l][mi1] + o.dp[mi2][r]); } } } } } return rt; } }; node bit[4 * N]; void ud(int id, int l, int r, int pos, int val){ if (l > pos || r < pos) return; if (l == r){ bit[id].b[0] += val; bit[id].b[1] += val; bit[id].dp[1][1] = abs(bit[id].b[0]); return; } int mid = (l + r) >> 1; ud(id * 2, l, mid, pos, val); ud(id * 2 + 1, mid + 1, r, pos, val); bit[id] = bit[id * 2] + bit[id * 2 + 1]; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); int n, m; cin >> n >> m; int lst = 0; for (int i = 1; i <= n; i++){ int val; cin >> val; if (i > 1) ud(1, 1, n - 1, i - 1, val - lst); lst = val; } while (m--){ int l, r, val; cin >> l >> r >> val; l--; if (l >= 1) ud(1, 1, n - 1, l, val); if (r <= n - 1) ud(1, 1, n - 1, r, -val); int res = 0; for (int i = 0; i <= 1; i++){ for (int j = 0; j <= 1; j++){ res = max(res, bit[1].dp[i][j]); } } cout << res << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...