Submission #993262

#TimeUsernameProblemLanguageResultExecution timeMemory
993262ghostlywalrusSjeckanje (COCI21_sjeckanje)C++17
0 / 110
14 ms37980 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; #define int long long #define PI pair<int,int> #define f first #define s second #define pb push_back #define szo(x) ((int)x.size()) #define all(a) (a).begin(), a.end() #define dbg(v) \ cout << "Line(" << _LINE << ") -> " << #v << " = " << (v) << endl; struct Data{ int pmin, pmax, smin, smax, cnt, total; Data() : pmin(0), pmax(0), smin(0), smax(0), cnt(0), total(0) {} }; const int maxn = 2e5+10; Data seg[4*maxn]; int lazy[4*maxn]; int nums[maxn]; int n; Data merge(Data &d1, Data &d2){ Data cur; cur.total = d1.total + d2.total; cur.cnt = d1.cnt + d2.cnt; cur.pmin = d1.pmin; cur.pmax = d1.pmax; cur.smin = d2.smin; cur.smax = d2.smax; if (d1.smax < d2.pmin || d1.smin > d2.pmax){ cur.total -= (d1.smax - d1.smin) + (d2.pmax - d2.pmin); int ma = max(d2.pmax, d1.smax), mi = min(d1.smin, d2.pmin); cur.total += ma - mi; cur.cnt -= 1; if (d1.cnt == 1) cur.pmin = mi, cur.pmax = ma; if (d2.cnt == 1) cur.smin = mi, cur.smax = ma; } return cur; } void build(int x = 1, int l = 0, int r = n - 1){ if (l == r){ seg[x].pmin = seg[x].pmax = seg[x].smin = seg[x].smax = nums[l]; seg[x].cnt = 1; seg[x].total = 0; return; } int tm = (l + r)/2; build(2*x, l, tm); build(2*x+1, tm+1, r); seg[x] = merge(seg[2*x], seg[2*x+1]); } void push(int x, int l, int r){ seg[x].pmin += lazy[x]; seg[x].pmax += lazy[x]; seg[x].smin += lazy[x]; seg[x].smax += lazy[x]; if (l != r) lazy[2*x] += lazy[x], lazy[2*x+1] += lazy[x]; lazy[x] = 0; } void update(int ql, int qr, int val, int x = 1, int l = 0, int r = n - 1){ push(x, l, r); if (qr < l || r < ql) return; if (ql <= l && r <= qr){ lazy[x] += val; push(x, l, r); return; } int tm = (l + r)/2; update(ql, qr, val, 2*x, l, tm); update(ql, qr, val, 2*x+1, tm+1, r); seg[x] = merge(seg[2*x], seg[2*x+1]); } int q; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> q; for (int i = 0; i < n; ++i) cin >> nums[i]; build(); while (q--){ int l, r, x; cin >> l >> r >> x; l--; r--; update(l, r, x); push(1, 0, n-1); cout << seg[1].total << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...