Submission #484413

#TimeUsernameProblemLanguageResultExecution timeMemory
484413HolyKProgression (NOI20_progression)C++17
0 / 100
793 ms153136 KiB
// Author: HolyK // Created: Wed Nov 3 16:27:37 2021 #include <bits/stdc++.h> template <class T, class U> inline bool smin(T &x, const U &y) { return y < x ? x = y, 1 : 0; } template <class T, class U> inline bool smax(T &x, const U &y) { return x < y ? x = y, 1 : 0; } using LL = long long; using PII = std::pair<int, int>; constexpr int N(3e5 + 5); int n, a[N]; #define ls o << 1 #define rs o << 1 | 1 struct SegTreeA { struct Line { LL k, b; Line(LL k = 0, LL b = 0) : k(k), b(b) {} bool empty() const { return k == 0 && b == 0; } void operator+=(const Line &r) { k += r.k, b += r.b; } LL f(LL x) { return k * x + b; } } t[N << 2], add[N << 2], cov[N << 2]; bool isCov[N << 2]; void applyAdd(int o, const Line &r) { t[o] += r; add[o] += r; } void applyCov(int o, const Line &r) { t[o] = r, add[o] = Line(), cov[o] = r; isCov[o] = true; } void pushdown(int o) { if (isCov[o]) { applyCov(ls, cov[o]), applyCov(rs, cov[o]); isCov[o] = false; } if (!add[o].empty()) { applyAdd(ls, add[o]), applyAdd(rs, add[o]); add[o] = Line(); } } void build(int o, int l, int r) { if (l == r) { t[o] = Line(0, a[l]); return; } int m = l + r >> 1; build(ls, l, m), build(rs, m + 1, r); } LL ask(int o, int l, int r, int x) { if (l == r) return t[o].f(l); int m = l + r >> 1; pushdown(o); return x <= m ? ask(ls, l, m, x) : ask(rs, m + 1, r, x); } void rangeAdd(int o, int l, int r, int x, int y, const Line &z) { if (x <= l && r <= y) return applyAdd(o, z); int m = l + r >> 1; pushdown(o); if (x <= m) rangeAdd(ls, l, m, x, y, z); if (y > m) rangeAdd(rs, m + 1, r, x, y, z); } void rangeCov(int o, int l, int r, int x, int y, const Line &z) { if (x <= l && r <= y) return applyCov(o, z); int m = l + r >> 1; pushdown(o); if (x <= m) rangeCov(ls, l, m, x, y, z); if (y > m) rangeCov(rs, m + 1, r, x, y, z); } } sta; struct SegTreeB { struct Info { int l; LL x; friend Info operator+(const Info &a, const Info &b) { if (a.l > 0 && b.l > 0 && a.x == b.x) return {a.l + b.l, a.x}; return {-1000000000, 0}; } bool operator<(const Info &r) const { return l < r.l; } void operator+=(LL r) { x += r; } }; struct Node { Info l, r, t, ans; int len; friend Node operator+(const Node &a, const Node &b) { return { std::max(a.l, a.t + b.l), std::max(b.r, b.t + a.r), a.t + b.t, std::max({a.ans, b.ans, a.r + b.l}), a.len + b.len }; } } t[N << 2]; LL cov[N << 2], add[N << 2]; bool isCov[N << 2]; void applyCov(int o, LL x) { t[o].l = t[o].r = t[o].t = t[o].ans = {t[o].len, x}; cov[o] = x; isCov[o] = true; add[o] = 0; } void applyAdd(int o, LL x) { t[o].l += x, t[o].r += x, t[o].t += x, t[o].ans += x; add[o] += x; } void pushdown(int o) { if (isCov[o]) { applyCov(ls, cov[o]), applyCov(rs, cov[o]); isCov[o] = false; } if (add[o]) { applyAdd(ls, add[o]), applyAdd(rs, add[o]); add[o] = 0; } } void pushup(int o) { t[o] = t[ls] + t[rs]; } void build(int o, int l, int r) { t[o].len = r - l + 1; if (l == r) { applyCov(o, a[l] - a[l - 1]); return; } int m = l + r >> 1; build(ls, l, m), build(rs, m + 1, r); pushup(o); } void rangeAdd(int o, int l, int r, int x, int y, LL z) { if (x <= l && r <= y) return applyAdd(o, z); int m = l + r >> 1; pushdown(o); if (x <= m) rangeAdd(ls, l, m, x, y, z); if (y > m) rangeAdd(rs, m + 1, r, x, y, z); pushup(o); } void rangeCov(int o, int l, int r, int x, int y, LL z) { if (x <= l && r <= y) return applyCov(o, z); int m = l + r >> 1; pushdown(o); if (x <= m) rangeCov(ls, l, m, x, y, z); if (y > m) rangeCov(rs, m + 1, r, x, y, z); pushup(o); } Node ask(int o, int l, int r, int x, int y) { if (x <= l && r <= y) return t[o]; int m = l + r >> 1; pushdown(o); if (y <= m) return ask(ls, l, m, x, y); if (x > m) return ask(rs, m + 1, r, x, y); return ask(ls, l, m, x, y) + ask(rs, m + 1, r, x, y); } } stb; int main() { // freopen("t.in", "r", stdin); // freopen(".out", "w", stdout); std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int q; std::cin >> n >> q; for (int i = 1; i <= n; i++) std::cin >> a[i]; sta.build(1, 1, n); stb.build(1, 2, n); // std::cerr << "build end\n"; while (q--) { int opt, l, r, x, y; std::cin >> opt >> l >> r; if (opt == 3) { std::cout << (l < r ? stb.ask(1, 2, n, l + 1, r).ans.l : 0) + 1 << "\n"; } else { std::cin >> x >> y; // std::cerr << opt << "\n"; if (opt == 1) { sta.rangeAdd(1, 1, n, l, r, SegTreeA::Line(y, x - 1LL * l * y)); // std::cerr << "rg\n"; if (l < r) stb.rangeAdd(1, 2, n, l + 1, r, y); } else { sta.rangeCov(1, 1, n, l, r, SegTreeA::Line(y, x - 1LL * l * y)); if (l < r) stb.rangeCov(1, 2, n, l + 1, r, y); } #define ask(x) sta.ask(1, 1, n, x) if (l > 1) { stb.rangeCov(1, 2, n, l, l, ask(l) - ask(l - 1)); } if (r < n) { stb.rangeCov(1, 2, n, r + 1, r + 1, ask(r + 1) - ask(r)); } // for (int i = 1; i <= n; i++) { // std::cerr << ask(i) << " \n"[i == n]; // } #undef ask } } return 0; }

Compilation message (stderr)

Progression.cpp: In member function 'void SegTreeA::build(int, int, int)':
Progression.cpp:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     int m = l + r >> 1;
      |             ~~^~~
Progression.cpp: In member function 'LL SegTreeA::ask(int, int, int, int)':
Progression.cpp:70:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     int m = l + r >> 1;
      |             ~~^~~
Progression.cpp: In member function 'void SegTreeA::rangeAdd(int, int, int, int, int, const SegTreeA::Line&)':
Progression.cpp:77:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |     int m = l + r >> 1;
      |             ~~^~~
Progression.cpp: In member function 'void SegTreeA::rangeCov(int, int, int, int, int, const SegTreeA::Line&)':
Progression.cpp:85:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |     int m = l + r >> 1;
      |             ~~^~~
Progression.cpp: In member function 'void SegTreeB::build(int, int, int)':
Progression.cpp:160:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  160 |     int m = l + r >> 1;
      |             ~~^~~
Progression.cpp: In member function 'void SegTreeB::rangeAdd(int, int, int, int, int, LL)':
Progression.cpp:167:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  167 |     int m = l + r >> 1;
      |             ~~^~~
Progression.cpp: In member function 'void SegTreeB::rangeCov(int, int, int, int, int, LL)':
Progression.cpp:176:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  176 |     int m = l + r >> 1;
      |             ~~^~~
Progression.cpp: In member function 'SegTreeB::Node SegTreeB::ask(int, int, int, int, int)':
Progression.cpp:185:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  185 |     int m = l + r >> 1;
      |             ~~^~~
#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...