Submission #1266228

#TimeUsernameProblemLanguageResultExecution timeMemory
1266228canhnam357Sjeckanje (COCI21_sjeckanje)C++20
110 / 110
589 ms29808 KiB
// source problem : #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define int long long #define lb lower_bound #define ub upper_bound #define MASK(i) (1LL << (i)) const int inf = 1e18; void ckmax(int& f, int s) { f = (f > s ? f : s); } void ckmin(int& f, int s) { f = (f < s ? f : s); } struct info { int tf, tb, a[2][2]; info() { tf = -1; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) a[i][j] = -inf; } } info (int x) { for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) a[i][j] = -inf; } if (x == 0) { tf = tb = 0; a[1][1] = 0; } if (x < 0) { tf = tb = 1; a[1][1] =-x; } if (x > 0) { tf = tb = 2; a[1][1] = x; } a[0][0] = 0; } int get() { return max({0LL, a[0][0], a[0][1], a[1][0], a[1][1]}); } void to_string() { cout << "DATA " << tf << ' ' << tf << ' ' << a[0][0] << ' ' << a[0][1] << ' ' << a[1][0] << ' ' << a[1][1] << '\n'; } }; info operator+(info a, info b) { if (a.tf < 0) return b; if (b.tf < 0) return a; //a.to_string(); //b.to_string(); info res; res.tf = a.tf; res.tb = b.tb; //res.to_string(); for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) { ckmax(res.a[i][j], a.a[i][j]); ckmax(res.a[i][j], b.a[i][j]); for (int c = 0; c < 2; c++) for (int d = 0; d < 2; d++) { if (a.a[i][j] < 0 || b.a[c][d] < 0) continue; if (j && c) { if ((a.tb == 1 && b.tf == 2) || (a.tb == 2 && b.tf == 1)) continue; ckmax(res.a[i][d], a.a[i][j] + b.a[c][d]); } else { ckmax(res.a[i][d], a.a[i][j] + b.a[c][d]); } } } // res.to_string(); // cout << '\n'; return res; } info st[1 << 19]; void update(int pos, int x, int id = 1, int l = 1, int r = 1 << 18) { if (l == r) { st[id] = info(x); return; } int mid = (l + r) >> 1; if (pos <= mid) update(pos, x, id << 1, l, mid); else update(pos, x, id << 1 | 1, mid + 1, r); st[id] = st[id << 1] + st[id << 1 | 1]; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector<int> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = n; i > 1; i--) { a[i] -= a[i - 1]; update(i, a[i]); } while (q--) { int l, r, x; cin >> l >> r >> x; if (l > 1) { a[l] += x; update(l, a[l]); } if (r < n) { a[r + 1] -= x; update(r + 1, a[r + 1]); } cout << st[1].get() << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...