Submission #1081553

#TimeUsernameProblemLanguageResultExecution timeMemory
1081553_callmelucianProgression (NOI20_progression)C++14
100 / 100
961 ms104608 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef tuple<int,int,int> tt; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) struct node { ll lazyAsgn, lazyAdd, sum; ll best, preLen, preVal, sufLen, sufVal, same, len; node() : lazyAsgn(0), lazyAdd(0), sum(0), best(0), preLen(0), preVal(0), sufLen(0), sufVal(0), same(0), len(0) {} void refine (node ln, node rn) { best = max({ln.best, rn.best, (ln.sufLen + rn.preLen) * (ln.sufVal == rn.preVal)}); preLen = max(ln.preLen, (ln.len + rn.preLen) * (ln.same == rn.preVal)); preVal = ln.preVal; sufLen = max(rn.sufLen, (ln.sufLen + rn.len) * (ln.sufVal == rn.same)); sufVal = rn.sufVal; same = (ln.same == rn.same ? ln.same : LLONG_MAX); sum = ln.sum + rn.sum, len = ln.len + rn.len; } void applyAsgn (ll val, int l, int r) { lazyAsgn = val, lazyAdd = 0, sum = val * ll(r - l + 1); best = preLen = sufLen = r - l + 1; preVal = sufVal = same = val, len = r - l + 1; } void applyAdd (ll incr, int l, int r) { lazyAdd += incr, sum += incr * ll(r - l + 1); preVal += incr, sufVal += incr, len = r - l + 1; if (same != LLONG_MAX) same += incr; } void pushDown (node &ln, node &rn, int l, int r, int mid) { if (lazyAsgn != LLONG_MAX) { ln.applyAsgn(lazyAsgn, l, mid); rn.applyAsgn(lazyAsgn, mid + 1, r); } if (lazyAdd != 0) { ln.applyAdd(lazyAdd, l, mid); rn.applyAdd(lazyAdd, mid + 1, r); } lazyAsgn = LLONG_MAX, lazyAdd = 0; } }; struct IT { vector<node> tr; IT (int sz) : tr(4 * sz) {} void rangeAssign (int a, int b, ll val, int k, int l, int r) { if (b < l || r < a) return; if (a <= l && r <= b) { tr[k].applyAsgn(val, l, r); return; } int mid = (l + r) >> 1; tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid); rangeAssign(a, b, val, 2 * k, l, mid); rangeAssign(a, b, val, 2 * k + 1, mid + 1, r); tr[k].refine(tr[2 * k], tr[2 * k + 1]); } void rangeAdd (int a, int b, ll incr, int k, int l, int r) { if (b < l || r < a) return; if (a <= l && r <= b) { tr[k].applyAdd(incr, l, r); return; } int mid = (l + r) >> 1; tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid); rangeAdd(a, b, incr, 2 * k, l, mid); rangeAdd(a, b, incr, 2 * k + 1, mid + 1, r); tr[k].refine(tr[2 * k], tr[2 * k + 1]); } ll querySum (int a, int b, int k, int l, int r) { if (b < l || r < a) return 0; if (a <= l && r <= b) return tr[k].sum; int mid = (l + r) >> 1; tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid); return querySum(a, b, 2 * k, l, mid) + querySum(a, b, 2 * k + 1, mid + 1, r); } node query (int a, int b, int k, int l, int r) { if (b < l || r < a) return node(); if (a <= l && r <= b) return tr[k]; int mid = (l + r) >> 1; tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid); node ans; ans.refine(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r)); return ans; } ll longestSame (int a, int b, int k, int l, int r) { return query(a, b, k, l, r).best; } void lineAssign (int a, int b, ll S, ll C, int k, int l, int r) { if (b < r) { ll incrR = querySum(1, b + 1, k, l, r) - (S + ll(b - a) * C); rangeAssign(b + 1, b + 1, incrR, k, l, r); } ll incrL = S - (a == l ? 0 : querySum(1, a - 1, k, l, r)); rangeAssign(a, a, incrL, k, l, r); if (a < b) rangeAssign(a + 1, b, C, k, l, r); } void lineAdd (int a, int b, ll S, ll C, int k, int l, int r) { if (b < r) rangeAdd(b + 1, b + 1, -(S + ll(b - a) * C), k, l, r); rangeAdd(a, a, S, k, l, r); if (a < b) rangeAdd(a + 1, b, C, k, l, r); } }; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; IT tree(n); for (int i = 1; i <= n; i++) { int D; cin >> D; tree.lineAssign(i, i, D, 0, 1, 1, n); } while (q--) { int type, L, R; cin >> type >> L >> R; if (type == 1) { int S, C; cin >> S >> C; tree.lineAdd(L, R, S, C, 1, 1, n); } else if (type == 2) { int S, C; cin >> S >> C; tree.lineAssign(L, R, S, C, 1, 1, n); } else { if (L == R) cout << 1 << "\n"; else cout << tree.longestSame(L + 1, R, 1, 1, n) + 1 << "\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...