oj.uz

Submission #1030009

# Submission time Handle Problem Language Result Execution time Memory
1030009 2024-07-21T15:49:06 Z avighna Progression (NOI20_progression) C++17
68 / 100
 1158 ms 111712 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);
      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);
        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 951 ms 102296 KB Output is correct
2 Correct 232 ms 592 KB Output is correct
3 Correct 200 ms 592 KB Output is correct
4 Correct 228 ms 592 KB Output is correct
5 Correct 202 ms 748 KB Output is correct
6 Correct 216 ms 816 KB Output is correct
7 Correct 222 ms 592 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 1008 ms 102356 KB Output is correct
12 Correct 1010 ms 102244 KB Output is correct
13 Correct 952 ms 102744 KB Output is correct
14 Correct 930 ms 102484 KB Output is correct
15 Correct 1006 ms 102480 KB Output is correct
16 Correct 986 ms 102184 KB Output is correct
17 Correct 953 ms 102084 KB Output is correct
18 Correct 997 ms 102116 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 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 398 ms 102736 KB Output is correct
2 Correct 82 ms 844 KB Output is correct
3 Correct 68 ms 852 KB Output is correct
4 Correct 51 ms 852 KB Output is correct
5 Correct 85 ms 1108 KB Output is correct
6 Correct 79 ms 1120 KB Output is correct
7 Correct 60 ms 952 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 392 ms 102480 KB Output is correct
12 Correct 370 ms 102736 KB Output is correct
13 Correct 355 ms 102484 KB Output is correct
14 Correct 410 ms 102412 KB Output is correct
15 Correct 378 ms 102644 KB Output is correct
16 Correct 366 ms 102992 KB Output is correct
17 Correct 386 ms 103004 KB Output is correct
18 Correct 377 ms 102992 KB Output is correct
19 Correct 372 ms 102260 KB Output is correct
20 Correct 354 ms 102376 KB Output is correct
21 Correct 324 ms 102280 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1065 ms 101800 KB Output is correct
2 Correct 229 ms 596 KB Output is correct
3 Correct 213 ms 4008 KB Output is correct
4 Correct 198 ms 3668 KB Output is correct
5 Correct 220 ms 3668 KB Output is correct
6 Correct 210 ms 3648 KB Output is correct
7 Correct 246 ms 3668 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1107 ms 108108 KB Output is correct
12 Correct 1137 ms 111576 KB Output is correct
13 Correct 1064 ms 108116 KB Output is correct
14 Correct 1157 ms 108272 KB Output is correct
15 Correct 1010 ms 111508 KB Output is correct
16 Correct 1140 ms 111572 KB Output is correct
17 Correct 1026 ms 111464 KB Output is correct
18 Correct 1069 ms 111712 KB Output is correct
19 Correct 1036 ms 111412 KB Output is correct
20 Correct 955 ms 111576 KB Output is correct
21 Correct 1000 ms 111332 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 102736 KB Output is correct
2 Correct 82 ms 844 KB Output is correct
3 Correct 68 ms 852 KB Output is correct
4 Correct 51 ms 852 KB Output is correct
5 Correct 85 ms 1108 KB Output is correct
6 Correct 79 ms 1120 KB Output is correct
7 Correct 60 ms 952 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 392 ms 102480 KB Output is correct
12 Correct 370 ms 102736 KB Output is correct
13 Correct 355 ms 102484 KB Output is correct
14 Correct 410 ms 102412 KB Output is correct
15 Correct 378 ms 102644 KB Output is correct
16 Correct 366 ms 102992 KB Output is correct
17 Correct 386 ms 103004 KB Output is correct
18 Correct 377 ms 102992 KB Output is correct
19 Correct 372 ms 102260 KB Output is correct
20 Correct 354 ms 102376 KB Output is correct
21 Correct 324 ms 102280 KB Output is correct
22 Correct 1029 ms 102104 KB Output is correct
23 Correct 169 ms 596 KB Output is correct
24 Correct 178 ms 740 KB Output is correct
25 Correct 177 ms 748 KB Output is correct
26 Correct 187 ms 592 KB Output is correct
27 Correct 208 ms 600 KB Output is correct
28 Correct 207 ms 724 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1089 ms 102136 KB Output is correct
33 Correct 1044 ms 101956 KB Output is correct
34 Correct 1156 ms 101980 KB Output is correct
35 Correct 1029 ms 101968 KB Output is correct
36 Correct 808 ms 102180 KB Output is correct
37 Correct 728 ms 102316 KB Output is correct
38 Correct 782 ms 102384 KB Output is correct
39 Correct 1055 ms 101900 KB Output is correct
40 Correct 1158 ms 101968 KB Output is correct
41 Correct 1111 ms 101984 KB Output is correct
42 Correct 1148 ms 101960 KB Output is correct
43 Correct 1122 ms 101984 KB Output is correct
44 Correct 1114 ms 101968 KB Output is correct
45 Correct 1050 ms 101968 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 951 ms 102296 KB Output is correct
2 Correct 232 ms 592 KB Output is correct
3 Correct 200 ms 592 KB Output is correct
4 Correct 228 ms 592 KB Output is correct
5 Correct 202 ms 748 KB Output is correct
6 Correct 216 ms 816 KB Output is correct
7 Correct 222 ms 592 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 1008 ms 102356 KB Output is correct
12 Correct 1010 ms 102244 KB Output is correct
13 Correct 952 ms 102744 KB Output is correct
14 Correct 930 ms 102484 KB Output is correct
15 Correct 1006 ms 102480 KB Output is correct
16 Correct 986 ms 102184 KB Output is correct
17 Correct 953 ms 102084 KB Output is correct
18 Correct 997 ms 102116 KB Output is correct
19 Correct 5 ms 600 KB Output is correct
20 Incorrect 2 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -