oj.uz

Submission #1030011

# Submission time Handle Problem Language Result Execution time Memory
1030011 2024-07-21T15:56:48 Z avighna Progression (NOI20_progression) C++17
68 / 100
 1186 ms 103100 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);
      }
    }
  };

  auto set_to_zero = [&](ll l) {
    ll pref_1 = diff_tree.query(0, l);
    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);
  };

  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;
      if (r - l <= 2) {
        for (ll i = l; i <= r; ++i) {
          set_to_zero(i);
        }
      } else {
        ll pref_1 = diff_tree.query(0, l);
        diff_tree.add(l, -pref_1);
        diff_tree.set(l + 1, r, 0);
        ll pref_2 = diff_tree.query(0, r + 1);
        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 949 ms 102304 KB Output is correct
2 Correct 220 ms 496 KB Output is correct
3 Correct 224 ms 724 KB Output is correct
4 Correct 223 ms 596 KB Output is correct
5 Correct 214 ms 732 KB Output is correct
6 Correct 220 ms 596 KB Output is correct
7 Correct 222 ms 596 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 961 ms 102172 KB Output is correct
12 Correct 952 ms 102260 KB Output is correct
13 Correct 943 ms 102500 KB Output is correct
14 Correct 938 ms 102496 KB Output is correct
15 Correct 913 ms 102480 KB Output is correct
16 Correct 934 ms 102136 KB Output is correct
17 Correct 913 ms 102092 KB Output is correct
18 Correct 986 ms 102124 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 323 ms 102740 KB Output is correct
2 Correct 81 ms 1024 KB Output is correct
3 Correct 57 ms 852 KB Output is correct
4 Correct 63 ms 908 KB Output is correct
5 Correct 79 ms 1108 KB Output is correct
6 Correct 61 ms 1104 KB Output is correct
7 Correct 74 ms 1124 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 358 ms 102388 KB Output is correct
12 Correct 318 ms 102644 KB Output is correct
13 Correct 351 ms 102452 KB Output is correct
14 Correct 347 ms 102348 KB Output is correct
15 Correct 315 ms 102732 KB Output is correct
16 Correct 349 ms 103100 KB Output is correct
17 Correct 370 ms 102924 KB Output is correct
18 Correct 380 ms 103004 KB Output is correct
19 Correct 293 ms 102224 KB Output is correct
20 Correct 331 ms 102312 KB Output is correct
21 Correct 330 ms 102340 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1038 ms 101880 KB Output is correct
2 Correct 228 ms 596 KB Output is correct
3 Correct 206 ms 596 KB Output is correct
4 Correct 238 ms 500 KB Output is correct
5 Correct 219 ms 592 KB Output is correct
6 Correct 225 ms 596 KB Output is correct
7 Correct 240 ms 472 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1059 ms 101984 KB Output is correct
12 Correct 1101 ms 102004 KB Output is correct
13 Correct 1056 ms 101792 KB Output is correct
14 Correct 1036 ms 101968 KB Output is correct
15 Correct 1042 ms 101816 KB Output is correct
16 Correct 976 ms 102028 KB Output is correct
17 Correct 1002 ms 101800 KB Output is correct
18 Correct 1070 ms 101968 KB Output is correct
19 Correct 1157 ms 101780 KB Output is correct
20 Correct 1132 ms 101988 KB Output is correct
21 Correct 1138 ms 101968 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 102740 KB Output is correct
2 Correct 81 ms 1024 KB Output is correct
3 Correct 57 ms 852 KB Output is correct
4 Correct 63 ms 908 KB Output is correct
5 Correct 79 ms 1108 KB Output is correct
6 Correct 61 ms 1104 KB Output is correct
7 Correct 74 ms 1124 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 358 ms 102388 KB Output is correct
12 Correct 318 ms 102644 KB Output is correct
13 Correct 351 ms 102452 KB Output is correct
14 Correct 347 ms 102348 KB Output is correct
15 Correct 315 ms 102732 KB Output is correct
16 Correct 349 ms 103100 KB Output is correct
17 Correct 370 ms 102924 KB Output is correct
18 Correct 380 ms 103004 KB Output is correct
19 Correct 293 ms 102224 KB Output is correct
20 Correct 331 ms 102312 KB Output is correct
21 Correct 330 ms 102340 KB Output is correct
22 Correct 1186 ms 101968 KB Output is correct
23 Correct 202 ms 596 KB Output is correct
24 Correct 230 ms 592 KB Output is correct
25 Correct 191 ms 736 KB Output is correct
26 Correct 224 ms 520 KB Output is correct
27 Correct 221 ms 596 KB Output is correct
28 Correct 202 ms 596 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1128 ms 102136 KB Output is correct
33 Correct 1085 ms 102020 KB Output is correct
34 Correct 1006 ms 102116 KB Output is correct
35 Correct 975 ms 102116 KB Output is correct
36 Correct 732 ms 102336 KB Output is correct
37 Correct 782 ms 102392 KB Output is correct
38 Correct 845 ms 102216 KB Output is correct
39 Correct 1115 ms 102104 KB Output is correct
40 Correct 1096 ms 101984 KB Output is correct
41 Correct 1149 ms 102148 KB Output is correct
42 Correct 1179 ms 102136 KB Output is correct
43 Correct 1153 ms 101892 KB Output is correct
44 Correct 1141 ms 101968 KB Output is correct
45 Correct 1112 ms 101968 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 949 ms 102304 KB Output is correct
2 Correct 220 ms 496 KB Output is correct
3 Correct 224 ms 724 KB Output is correct
4 Correct 223 ms 596 KB Output is correct
5 Correct 214 ms 732 KB Output is correct
6 Correct 220 ms 596 KB Output is correct
7 Correct 222 ms 596 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 961 ms 102172 KB Output is correct
12 Correct 952 ms 102260 KB Output is correct
13 Correct 943 ms 102500 KB Output is correct
14 Correct 938 ms 102496 KB Output is correct
15 Correct 913 ms 102480 KB Output is correct
16 Correct 934 ms 102136 KB Output is correct
17 Correct 913 ms 102092 KB Output is correct
18 Correct 986 ms 102124 KB Output is correct
19 Correct 3 ms 604 KB Output is correct
20 Incorrect 2 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -