제출 #1127983

#제출 시각아이디문제언어결과실행 시간메모리
1127983notkaiSjeckanje (COCI21_sjeckanje)C++20
0 / 110
2 ms1856 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 200000 using i1 = long long; vector<i1> diff(MAXN-1); bool opposite(i1 x, i1 y) { if (x>0 && y < 0) { return true; } if (x < 0 && y > 0) { return true; } return false; } namespace SegmentTree{ i1 segtree[MAXN * 4][4]; i1 n; void update(i1 index, i1 value, i1 onleft=0, i1 onright=n-1, i1 treeindex=0){ if (onleft > index || onright < index){ return; } if (onleft == onright){ segtree[treeindex][0] = abs(value); segtree[treeindex][1] = -1; segtree[treeindex][2] = -1; segtree[treeindex][3] = 0; return; } update(index, value, onleft, (onleft+onright)/2, treeindex*2+1); update(index, value, (onleft+onright+2)/2, onright, treeindex*2+2); segtree[treeindex][0] = -1; segtree[treeindex][1] = -1; segtree[treeindex][2] = -1; segtree[treeindex][3] = -1; for (i1 i = 0; i < 4; i++) { for (i1 j = 0; j < 4; j++) { if (segtree[treeindex*2+1][i] == -1 || segtree[treeindex*2+2][j] == -1) { continue; } if ((opposite(diff[(onleft+onright)/2], diff[(onleft+onright+2)/2])) && (i%2==0) && (j/2 == 0)) { continue; } segtree[treeindex][2*(i/2) + (j%2)] = segtree[treeindex*2+1][i] + segtree[treeindex*2+2][j]; } } } void initialize(i1 maxn){ n = maxn; for (i1 i = 0; i < 4*n; i++){ segtree[i][0] = 0; segtree[i][1] = 0; segtree[i][2] = 0; segtree[i][3] = 0; } } } //addition, 1 based indexing, range queries + point updates int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); i1 n,q; cin >> n >> q; vector<i1> arr(n); for (i1 i = 0; i < n; i++) { cin >> arr[i]; if (i > 0) { diff[i-1] = arr[i] - arr[i-1]; } } SegmentTree::initialize(n-1); for (i1 i = 0; i < n-1; i++) { SegmentTree::update(i, diff[i]); } for (i1 query = 0; query < q; query++) { i1 l,r,x; cin >> l >> r >> x; l -= 1; r -= 1; if (r < n-1) { diff[r] -= x; SegmentTree::update(r, diff[r]); } if (l > 0) { diff[l-1] += x; SegmentTree::update(l-1, diff[l-1]); } //value is new value not diff i1 maxans = 0; for (i1 i = 0; i < 4; i++) { maxans = max(maxans, SegmentTree::segtree[0][i]); } cout << maxans << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...