oj.uz

Submission #484413

# Submission time Handle Problem Language Result Execution time Memory
484413 2021-11-03T09:19:12 Z HolyK Progression (NOI20_progression) C++17
0 / 100
 793 ms 153136 KB 
// 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

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;
      |             ~~^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 145492 KB Output is correct
2 Correct 96 ms 57116 KB Output is correct
3 Correct 91 ms 57136 KB Output is correct
4 Correct 95 ms 57032 KB Output is correct
5 Correct 100 ms 57220 KB Output is correct
6 Correct 92 ms 57128 KB Output is correct
7 Correct 92 ms 57028 KB Output is correct
8 Runtime error 65 ms 114932 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 56828 KB Output is correct
2 Correct 21 ms 56652 KB Output is correct
3 Correct 22 ms 56716 KB Output is correct
4 Correct 22 ms 56688 KB Output is correct
5 Runtime error 87 ms 114828 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 149376 KB Output is correct
2 Correct 107 ms 59352 KB Output is correct
3 Correct 99 ms 59376 KB Output is correct
4 Correct 85 ms 59332 KB Output is correct
5 Correct 97 ms 59584 KB Output is correct
6 Correct 103 ms 59448 KB Output is correct
7 Correct 98 ms 59640 KB Output is correct
8 Runtime error 66 ms 114888 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 793 ms 153136 KB Output is correct
2 Correct 164 ms 59972 KB Output is correct
3 Correct 172 ms 60172 KB Output is correct
4 Correct 172 ms 60048 KB Output is correct
5 Correct 169 ms 60032 KB Output is correct
6 Correct 175 ms 59976 KB Output is correct
7 Correct 177 ms 60048 KB Output is correct
8 Runtime error 72 ms 114900 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 149376 KB Output is correct
2 Correct 107 ms 59352 KB Output is correct
3 Correct 99 ms 59376 KB Output is correct
4 Correct 85 ms 59332 KB Output is correct
5 Correct 97 ms 59584 KB Output is correct
6 Correct 103 ms 59448 KB Output is correct
7 Correct 98 ms 59640 KB Output is correct
8 Runtime error 66 ms 114888 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 145492 KB Output is correct
2 Correct 96 ms 57116 KB Output is correct
3 Correct 91 ms 57136 KB Output is correct
4 Correct 95 ms 57032 KB Output is correct
5 Correct 100 ms 57220 KB Output is correct
6 Correct 92 ms 57128 KB Output is correct
7 Correct 92 ms 57028 KB Output is correct
8 Runtime error 65 ms 114932 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -