Submission #1012635

#TimeUsernameProblemLanguageResultExecution timeMemory
1012635gygSjeckanje (COCI21_sjeckanje)C++17
0 / 110
1 ms4444 KiB
#include <bits/stdc++.h> using namespace std; using lint = long long; const int MAX_N = 2e5 + 5; const lint INF = 1e18; int n, q; array<lint, MAX_N> a; struct Node { lint val; lint maxmax, maxmin, minmax, minmin; lint l_max, l_min, r_max, r_min; } st[4 * MAX_N]; lint lazy[4 * MAX_N]; void propogate(int u) { if (lazy[u] == 0) return; for (int v : {2 * u, 2 * u + 1}) { st[v].l_max += lazy[u], st[v].r_max += lazy[u]; st[v].l_min -= lazy[u], st[v].r_min -= lazy[u]; st[v].maxmax += 2 * lazy[u], st[v].minmin -= 2 * lazy[u]; } lazy[u] = 0; } Node merge(Node& x, Node& y) { Node ans; ans.val = max({x.val + y.val, x.r_min + y.l_max, x.r_max + y.l_min}); ans.maxmax = max({x.l_max + y.r_max, x.maxmax + y.minmax, x.maxmin + y.maxmax}); ans.maxmin = max({x.l_max + y.r_min, x.maxmax + y.minmin, x.maxmin + y.maxmin}); ans.minmax = max({x.l_min + y.r_max, x.minmax + y.minmax, x.minmin + y.maxmax}); ans.minmin = max({x.l_min + y.r_min, x.minmax + y.minmin, x.minmin + y.maxmin}); ans.l_max = max({x.l_max + y.val, x.maxmax + y.l_min, x.maxmin + y.l_max}); ans.l_min = max({x.l_min + y.val, x.minmax + y.l_min, x.minmin + y.l_max}); ans.r_max = max({x.val + y.r_max, x.r_max + y.minmax, x.r_min + y.maxmax}); ans.r_min = max({x.val + y.r_min, x.r_max + y.minmin, x.r_min + y.maxmin}); return ans; } void build(int u = 1, int lo = 1, int hi = n) { if (lo == hi) { st[u].val = 0; st[u].l_max = st[u].r_max = a[lo]; st[u].l_min = st[u].r_min = -a[lo]; st[u].maxmax = st[u].maxmin = st[u].minmax = st[u].minmin = -INF; return; } int mid = (lo + hi) / 2; build(2 * u, lo, mid), build(2 * u + 1, mid + 1, hi); st[u] = merge(st[2 * u], st[2 * u + 1]); } void update(int l, int r, lint x, int u = 1, int lo = 1, int hi = n) { if (r < lo || hi < l) return; if (l <= lo && hi <= r) { st[u].l_max += x, st[u].r_max += x; st[u].l_min -= x, st[u].r_min -= x; st[u].maxmax += 2 * x, st[u].minmin -= 2 * x; lazy[u] += x; return; } propogate(u); int mid = (lo + hi) / 2; update(l, r, x, 2 * u, lo, mid), update(l, r, x, 2 * u + 1, mid + 1, hi); st[u] = merge(st[2 * u], st[2 * u + 1]); } void debug(int u = 1, int lo = 1, int hi = n) { cout << lo << " " << hi << ": " << endl; cout << "VAL " << st[u].val << endl; cout << "MAXMAX " << st[u].maxmax << endl; cout << "MAXMIN " << st[u].maxmin << endl; cout << "MINMAX " << st[u].minmax << endl; cout << "MINMIN " << st[u].minmin << endl; cout << "LMAX " << st[u].l_max << endl; cout << "LMIN " << st[u].l_min << endl; cout << "RMAX " << st[u].r_max << endl; cout << "RMIN " << st[u].r_min << endl; if (lo == hi) return; int mid = (lo + hi) / 2; debug(2 * u, lo, mid), debug(2 * u + 1, mid + 1, hi); } int main() { // freopen("sje.in", "r", stdin); cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i]; build(); for (int i = 1; i <= q; i++) { int l, r; cin >> l >> r; lint x; cin >> x; update(l, r, x); // if (i == q) debug(); cout << st[1].val << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...