oj.uz

Submission #1030006

# Submission time Handle Problem Language Result Execution time Memory
1030006 2024-07-21T15:46:22 Z avighna Progression (NOI20_progression) C++17
57 / 100
 1252 ms 111344 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);
      ll pref_2 = diff_tree.query(0, r + 1);
      diff_tree.add(l, -pref_1);
      diff_tree.set(l + 1, r, 0);
      diff_tree.add(r + 1, pref_2);
      tree.update(l + 1, -diff_tree.query(l + 1, l + 1));
      tree.zero_range(l + 2, r);
      tree.update(r + 1, diff_tree.query(r + 1, r + 1));
      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 992 ms 110308 KB Output is correct
2 Correct 274 ms 3620 KB Output is correct
3 Correct 240 ms 3632 KB Output is correct
4 Correct 236 ms 3648 KB Output is correct
5 Correct 221 ms 3668 KB Output is correct
6 Correct 241 ms 3516 KB Output is correct
7 Correct 233 ms 3432 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1066 ms 110128 KB Output is correct
12 Correct 1134 ms 110140 KB Output is correct
13 Correct 1093 ms 110412 KB Output is correct
14 Correct 1058 ms 110452 KB Output is correct
15 Correct 1079 ms 110408 KB Output is correct
16 Correct 1133 ms 110156 KB Output is correct
17 Correct 1027 ms 110128 KB Output is correct
18 Correct 1029 ms 110076 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 600 KB Output is correct
2 Incorrect 1 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 428 ms 108572 KB Output is correct
2 Correct 90 ms 2960 KB Output is correct
3 Correct 73 ms 3156 KB Output is correct
4 Correct 61 ms 3116 KB Output is correct
5 Correct 109 ms 3156 KB Output is correct
6 Correct 89 ms 3256 KB Output is correct
7 Correct 79 ms 3268 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 477 ms 107196 KB Output is correct
12 Correct 418 ms 108624 KB Output is correct
13 Correct 450 ms 107332 KB Output is correct
14 Correct 421 ms 107252 KB Output is correct
15 Correct 402 ms 108624 KB Output is correct
16 Correct 455 ms 109300 KB Output is correct
17 Correct 444 ms 109132 KB Output is correct
18 Correct 381 ms 109328 KB Output is correct
19 Correct 401 ms 108568 KB Output is correct
20 Correct 357 ms 108524 KB Output is correct
21 Correct 348 ms 108648 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1164 ms 111344 KB Output is correct
2 Incorrect 243 ms 3676 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 428 ms 108572 KB Output is correct
2 Correct 90 ms 2960 KB Output is correct
3 Correct 73 ms 3156 KB Output is correct
4 Correct 61 ms 3116 KB Output is correct
5 Correct 109 ms 3156 KB Output is correct
6 Correct 89 ms 3256 KB Output is correct
7 Correct 79 ms 3268 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 477 ms 107196 KB Output is correct
12 Correct 418 ms 108624 KB Output is correct
13 Correct 450 ms 107332 KB Output is correct
14 Correct 421 ms 107252 KB Output is correct
15 Correct 402 ms 108624 KB Output is correct
16 Correct 455 ms 109300 KB Output is correct
17 Correct 444 ms 109132 KB Output is correct
18 Correct 381 ms 109328 KB Output is correct
19 Correct 401 ms 108568 KB Output is correct
20 Correct 357 ms 108524 KB Output is correct
21 Correct 348 ms 108648 KB Output is correct
22 Correct 1249 ms 111016 KB Output is correct
23 Correct 200 ms 3668 KB Output is correct
24 Correct 194 ms 3644 KB Output is correct
25 Correct 189 ms 3524 KB Output is correct
26 Correct 227 ms 3464 KB Output is correct
27 Correct 192 ms 3664 KB Output is correct
28 Correct 224 ms 3668 KB Output is correct
29 Correct 1 ms 600 KB Output is correct
30 Correct 1 ms 472 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1252 ms 108212 KB Output is correct
33 Correct 1157 ms 110952 KB Output is correct
34 Correct 1124 ms 108108 KB Output is correct
35 Correct 1149 ms 108196 KB Output is correct
36 Correct 810 ms 107876 KB Output is correct
37 Correct 857 ms 108012 KB Output is correct
38 Correct 828 ms 107852 KB Output is correct
39 Correct 1129 ms 110928 KB Output is correct
40 Correct 1164 ms 111032 KB Output is correct
41 Correct 1184 ms 110936 KB Output is correct
42 Correct 1133 ms 110932 KB Output is correct
43 Correct 1162 ms 110884 KB Output is correct
44 Correct 1169 ms 110880 KB Output is correct
45 Correct 1069 ms 110876 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 110308 KB Output is correct
2 Correct 274 ms 3620 KB Output is correct
3 Correct 240 ms 3632 KB Output is correct
4 Correct 236 ms 3648 KB Output is correct
5 Correct 221 ms 3668 KB Output is correct
6 Correct 241 ms 3516 KB Output is correct
7 Correct 233 ms 3432 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1066 ms 110128 KB Output is correct
12 Correct 1134 ms 110140 KB Output is correct
13 Correct 1093 ms 110412 KB Output is correct
14 Correct 1058 ms 110452 KB Output is correct
15 Correct 1079 ms 110408 KB Output is correct
16 Correct 1133 ms 110156 KB Output is correct
17 Correct 1027 ms 110128 KB Output is correct
18 Correct 1029 ms 110076 KB Output is correct
19 Correct 5 ms 600 KB Output is correct
20 Incorrect 1 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -