oj.uz

Submission #1029962

# Submission time Handle Problem Language Result Execution time Memory
1029962 2024-07-21T14:48:34 Z avighna Progression (NOI20_progression) C++17
57 / 100
 1201 ms 109448 KB 
#include <bits/stdc++.h>

typedef long long ll;

class Node {
public:
  ll pref, suff, max;
  ll ele;
  ll size;

  Node(ll pref, ll suff, ll max, ll ele, ll size)
      : pref(pref), suff(suff), max(max), ele(ele), size(size) {}
  Node() : pref(0), suff(0), max(0), ele(-1), size(0) {}

  bool operator==(const Node &other) {
    return pref == other.pref and suff == other.suff and max == other.max and
           ele == other.ele and size == other.size;
  }
};

class SegmentTree {
public:
  std::vector<Node> seg;
  std::vector<bool> lazy;
  ll n;

  SegmentTree(ll n) {
    this->n = n;
    seg.resize(4 * n);
    lazy.resize(8 * n);
  }

  Node idt() { return Node(0, 0, 0, -1, 0); }

  Node f(Node a, Node b) {
    if (a == idt()) {
      return b;
    }
    if (b == idt()) {
      return a;
    }
    Node ans;
    ans.pref = a.pref;
    if (a.pref == a.size) {
      ans.pref += b.pref;
    }
    ans.suff = b.suff;
    if (b.suff == b.size) {
      ans.suff += a.suff;
    }
    ans.max = std::max(ans.max, ans.suff);
    ans.max = std::max(ans.max, ans.pref);
    ans.max = std::max(ans.max, a.suff + b.pref);
    ans.max = std::max(ans.max, a.max);
    ans.max = std::max(ans.max, b.max);
    ans.ele = a.ele;
    ans.size = a.size + b.size;
    return ans;
  }

  void construct(std::vector<ll> &a, ll v, ll tl, ll tr) {
    if (tl == tr) {
      if (a[tl] == 0) {
        seg[v] = Node(1, 1, 1, a[tl], 1);
      } else {
        seg[v] = Node(0, 0, 0, a[tl], 1);
      }
      return;
    }
    ll tm = (tl + tr) / 2;
    construct(a, 2 * v, tl, tm);
    construct(a, 2 * v + 1, tm + 1, tr);
    seg[v] = f(seg[2 * v], seg[2 * v + 1]);
  }

  void lazy_update(ll v, ll tl, ll tr) {
    if (lazy[v]) {
      lazy[v] = false;
      ll size = tr - tl + 1;
      seg[v] = Node(size, size, size, 0, size);
      lazy[2 * v] = lazy[2 * v + 1] = true;
    }
  }

  Node query(ll v, ll tl, ll tr, ll l, ll r) {
    lazy_update(v, tl, tr);
    if (tl > tr || l > r || tr < l || r < tl) {
      return idt();
    }
    if (l <= tl && tr <= r) {
      return seg[v];
    }
    ll tm = (tl + tr) / 2;
    return f(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm + 1, tr, l, r));
  }
  Node query(ll l, ll r) { return query(1, 0, n, l, r); }

  void update(ll v, ll tl, ll tr, ll idx, ll del) {
    lazy_update(v, tl, tr);
    if (tl > tr || (!(tl <= idx && idx <= tr))) {
      return;
    }
    if (tl != tr) {
      ll tm = (tl + tr) / 2;
      update(2 * v, tl, tm, idx, del);
      update(2 * v + 1, tm + 1, tr, idx, del);
      seg[v] = f(seg[2 * v], seg[2 * v + 1]);
    } else {
      seg[v].ele += del;
      if (seg[v].ele == 0) {
        seg[v] = Node(1, 1, 1, seg[v].ele, 1);
      } else {
        seg[v] = Node(0, 0, 0, seg[v].ele, 1);
      }
    }
  }
  void update(ll idx, ll del) { update(1, 0, n, idx, del); }

  void zero_range(ll v, ll tl, ll tr, ll l, ll r) {
    lazy_update(v, tl, tr);
    if (tl > tr || l > r || tr < l || r < tl) {
      return;
    }
    if (l <= tl && tr <= r) {
      ll size = tr - tl + 1;
      seg[v] = Node(size, size, size, 0, size);
      lazy[2 * v] = lazy[2 * v + 1] = true;
      return;
    }
    ll tm = (tl + tr) / 2;
    zero_range(2 * v, tl, tm, l, r);
    zero_range(2 * v + 1, tm + 1, tr, l, r);
  }
  void zero_range(ll l, ll r) { zero_range(1, 0, n, l, r); }
};

class LazySegmentTree {
private:
  enum type { ADD, SET };
  std::vector<std::array<ll, 2>> lazy;

public:
  std::vector<ll> seg;
  ll n;

  ll f(ll a, ll b) { return a + b; }
  // For a bitwise AND, this would be 1, since x AND x = x (and not 2x)
  ll f_update_range(ll size) { return size; }
  ll idt() { return 0; }

  LazySegmentTree(ll n) {
    this->n = n;
    seg.resize(4 * n, idt());
    lazy.resize(8 * n);
    for (ll i = 0; i < 8 * n; ++i) {
      lazy[i][SET] = -1;
    }
  }

  void do_lazy_update(ll v, ll size) {
    if (lazy[v][SET] != -1) {
      seg[v] = lazy[v][SET] * size;
      lazy[2 * v][SET] = lazy[2 * v + 1][SET] = lazy[v][SET];
      lazy[2 * v][ADD] = lazy[2 * v + 1][ADD] = 0;
      lazy[v][SET] = -1;
    }
    if (lazy[v][ADD] != 0) {
      seg[v] += lazy[v][ADD] * size;
      lazy[2 * v][ADD] += lazy[v][ADD];
      lazy[2 * v + 1][ADD] += lazy[v][ADD];
      lazy[v][ADD] = 0;
    }
  }

  void add(ll v, ll tl, ll tr, ll l, ll r, ll delta) {
    ll size = f_update_range(tr - tl + 1);
    do_lazy_update(v, size);
    // [tl, tr] ... [l, r] or [l, r] ... [tl, tr]
    if (tr < l || r < tl || l > r || tl > tr) {
      return;
    }
    // [l, [tl, tr], r]
    if (l <= tl && tr <= r) {
      seg[v] += delta * size;
      lazy[2 * v][ADD] += delta;
      lazy[2 * v + 1][ADD] += delta;
      return;
    }
    ll tm = (tl + tr) / 2;
    add(2 * v, tl, tm, l, r, delta);
    add(2 * v + 1, tm + 1, tr, l, r, delta);
    seg[v] = f(seg[2 * v], seg[2 * v + 1]);
  }
  void add(ll l, ll r, ll delta) { add(1, 0, n, l, r, delta); }
  void add(ll idx, ll delta) { add(idx, idx, delta); }

  void set(ll v, ll tl, ll tr, ll l, ll r, ll x) {
    ll size = f_update_range(tr - tl + 1);
    do_lazy_update(v, size);
    // [tl, tr] ... [l, r] or [l, r] ... [tl, tr]
    if (tr < l || r < tl || l > r || tl > tr) {
      return;
    }
    // [l, [tl, tr], r]
    if (l <= tl && tr <= r) {
      seg[v] = x * size;
      lazy[2 * v][SET] = lazy[2 * v + 1][SET] = x;
      lazy[2 * v][ADD] = lazy[2 * v + 1][ADD] = 0;
      return;
    }
    ll tm = (tl + tr) / 2;
    set(2 * v, tl, tm, l, r, x);
    set(2 * v + 1, tm + 1, tr, l, r, x);
    seg[v] = f(seg[2 * v], seg[2 * v + 1]);
  }
  void set(ll l, ll r, ll x) { set(1, 0, n, l, r, x); }
  void set(ll idx, ll x) { set(idx, idx, x); }

  ll query(ll v, ll tl, ll tr, ll l, ll r) {
    do_lazy_update(v, f_update_range(tr - tl + 1));
    // [tl, tr] ... [l, r] or [l, r] ... [tl, tr]
    if (tr < l || r < tl || l > r || tl > tr) {
      return idt();
    }
    // [l, [tl, tr], r]
    if (l <= tl && tr <= r) {
      return seg[v];
    }
    ll tm = (tl + tr) / 2;
    return f(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm + 1, tr, l, r));
  }
  ll query(ll l, ll r) { return query(1, 0, n, l, r); }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n, q;
  std::cin >> n >> q;
  std::vector<ll> d(n + 1);
  for (ll i = 0; i < n; ++i) {
    std::cin >> d[i];
  }
  std::vector<ll> diff(n + 1);
  std::adjacent_difference(d.begin(), d.end(), diff.begin());
  std::vector<ll> diff_diff(n + 1);
  std::adjacent_difference(diff.begin(), diff.end(), diff_diff.begin());

  SegmentTree tree(n);
  LazySegmentTree diff_tree(n);
  tree.construct(diff_diff, 1, 0, n);
  for (ll i = 0; i < n; ++i) {
    diff_tree.add(i, diff[i]);
  }

  auto diff_update = [&](ll l, ll r, ll s, ll c) {
    diff_tree.add(l, s);
    diff_tree.add(r + 1, -s - (r - l) * c);
    if (l + 1 <= r) {
      diff_tree.add(l + 1, r, c);
    }
  };

  auto update = [&](ll l, ll r, ll s, ll c) {
    tree.update(l, s);
    tree.update(l + 1, -s);
    tree.update(r + 1, -s);
    if (r + 2 <= n) {
      tree.update(r + 2, s);
    }
    if (l != r) {
      tree.update(l + 1, c);
      tree.update(r + 1, -c - (r - l) * c);
      if (r + 2 <= n) {
        tree.update(r + 2, (r - l) * c);
      }
    }
  };

  while (q--) {
    ll t;
    std::cin >> t;
    ll l, r;
    std::cin >> l >> r;
    --l, --r;
    if (t == 1) {
      ll s, c;
      std::cin >> s >> c;
      update(l, r, s, c);
      diff_update(l, r, s, c);
    } else if (t == 2) {
      ll s, c;
      std::cin >> s >> c;
      ll pref_1 = diff_tree.query(0, l - 1);
      ll pref_2 = diff_tree.query(0, r - 1);
      if (l == r) {
        diff_tree.add(l, -pref_1);
        diff_tree.add(l + 1, pref_1);
        tree.update(l, -pref_1);
        tree.update(l + 1, 2 * pref_1);
        tree.update(l + 2, -pref_1);
      } else {
        diff_tree.add(l, -pref_1);
        diff_tree.set(l + 1, r, 0);
        diff_tree.add(r, pref_2);
        tree.update(l, -pref_1);
        tree.update(l + 1, pref_1);
        tree.zero_range(l + 2, r);
        tree.update(r + 1, pref_2);
        tree.update(r + 2, -pref_2);
      }
      update(l, r, s, c);
      diff_update(l, r, s, c);
    } else {
      if (l + 2 > r) {
        std::cout << r - l + 1 << '\n';
      } else {
        std::cout << tree.query(l + 2, r).max + 2 << '\n';
      }
    }
  }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 108560 KB Output is correct
2 Correct 237 ms 3088 KB Output is correct
3 Correct 231 ms 3140 KB Output is correct
4 Correct 239 ms 3152 KB Output is correct
5 Correct 239 ms 3136 KB Output is correct
6 Correct 229 ms 3152 KB Output is correct
7 Correct 234 ms 3076 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 954 ms 108736 KB Output is correct
12 Correct 966 ms 108620 KB Output is correct
13 Correct 1006 ms 108908 KB Output is correct
14 Correct 1016 ms 109000 KB Output is correct
15 Correct 994 ms 108668 KB Output is correct
16 Correct 1012 ms 108700 KB Output is correct
17 Correct 958 ms 108648 KB Output is correct
18 Correct 952 ms 108508 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Incorrect 2 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 107460 KB Output is correct
2 Correct 79 ms 2872 KB Output is correct
3 Correct 71 ms 2900 KB Output is correct
4 Correct 58 ms 2880 KB Output is correct
5 Correct 79 ms 3000 KB Output is correct
6 Correct 71 ms 2988 KB Output is correct
7 Correct 83 ms 3024 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 391 ms 106524 KB Output is correct
12 Correct 395 ms 107600 KB Output is correct
13 Correct 384 ms 106428 KB Output is correct
14 Correct 357 ms 106548 KB Output is correct
15 Correct 332 ms 107456 KB Output is correct
16 Correct 404 ms 108120 KB Output is correct
17 Correct 426 ms 108160 KB Output is correct
18 Correct 342 ms 108112 KB Output is correct
19 Correct 348 ms 107436 KB Output is correct
20 Correct 304 ms 107456 KB Output is correct
21 Correct 316 ms 107604 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1114 ms 109448 KB Output is correct
2 Incorrect 224 ms 3408 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 107460 KB Output is correct
2 Correct 79 ms 2872 KB Output is correct
3 Correct 71 ms 2900 KB Output is correct
4 Correct 58 ms 2880 KB Output is correct
5 Correct 79 ms 3000 KB Output is correct
6 Correct 71 ms 2988 KB Output is correct
7 Correct 83 ms 3024 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 391 ms 106524 KB Output is correct
12 Correct 395 ms 107600 KB Output is correct
13 Correct 384 ms 106428 KB Output is correct
14 Correct 357 ms 106548 KB Output is correct
15 Correct 332 ms 107456 KB Output is correct
16 Correct 404 ms 108120 KB Output is correct
17 Correct 426 ms 108160 KB Output is correct
18 Correct 342 ms 108112 KB Output is correct
19 Correct 348 ms 107436 KB Output is correct
20 Correct 304 ms 107456 KB Output is correct
21 Correct 316 ms 107604 KB Output is correct
22 Correct 1161 ms 109080 KB Output is correct
23 Correct 218 ms 3156 KB Output is correct
24 Correct 175 ms 3168 KB Output is correct
25 Correct 195 ms 3204 KB Output is correct
26 Correct 200 ms 3156 KB Output is correct
27 Correct 190 ms 3152 KB Output is correct
28 Correct 193 ms 3184 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1145 ms 106772 KB Output is correct
33 Correct 1182 ms 108792 KB Output is correct
34 Correct 1137 ms 106824 KB Output is correct
35 Correct 1172 ms 106908 KB Output is correct
36 Correct 877 ms 106740 KB Output is correct
37 Correct 766 ms 106836 KB Output is correct
38 Correct 835 ms 106948 KB Output is correct
39 Correct 1111 ms 108860 KB Output is correct
40 Correct 1108 ms 109096 KB Output is correct
41 Correct 1158 ms 109104 KB Output is correct
42 Correct 1193 ms 109060 KB Output is correct
43 Correct 1201 ms 108972 KB Output is correct
44 Correct 1195 ms 108768 KB Output is correct
45 Correct 1141 ms 108916 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 108560 KB Output is correct
2 Correct 237 ms 3088 KB Output is correct
3 Correct 231 ms 3140 KB Output is correct
4 Correct 239 ms 3152 KB Output is correct
5 Correct 239 ms 3136 KB Output is correct
6 Correct 229 ms 3152 KB Output is correct
7 Correct 234 ms 3076 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 954 ms 108736 KB Output is correct
12 Correct 966 ms 108620 KB Output is correct
13 Correct 1006 ms 108908 KB Output is correct
14 Correct 1016 ms 109000 KB Output is correct
15 Correct 994 ms 108668 KB Output is correct
16 Correct 1012 ms 108700 KB Output is correct
17 Correct 958 ms 108648 KB Output is correct
18 Correct 952 ms 108508 KB Output is correct
19 Correct 4 ms 604 KB Output is correct
20 Incorrect 2 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -