oj.uz

Submission #1030018

# Submission time Handle Problem Language Result Execution time Memory
1030018 2024-07-21T16:12:12 Z avighna Progression (NOI20_progression) C++17
68 / 100
 1201 ms 107280 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 {
        diff_tree.add(l, -diff_tree.query(0, l - 1));
        diff_tree.set(l + 1, r, 0);
        diff_tree.add(r + 1, diff_tree.query(0, r + 1));
        tree.update(l + 1, -diff_tree.query(l, l));
        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 1016 ms 106684 KB Output is correct
2 Correct 250 ms 2384 KB Output is correct
3 Correct 213 ms 2532 KB Output is correct
4 Correct 233 ms 2500 KB Output is correct
5 Correct 232 ms 2464 KB Output is correct
6 Correct 253 ms 2584 KB Output is correct
7 Correct 222 ms 2384 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 992 ms 106636 KB Output is correct
12 Correct 1004 ms 106452 KB Output is correct
13 Correct 1046 ms 106796 KB Output is correct
14 Correct 981 ms 106792 KB Output is correct
15 Correct 969 ms 106676 KB Output is correct
16 Correct 1016 ms 106460 KB Output is correct
17 Correct 1002 ms 106500 KB Output is correct
18 Correct 991 ms 106636 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 397 ms 106180 KB Output is correct
2 Correct 80 ms 2184 KB Output is correct
3 Correct 76 ms 2108 KB Output is correct
4 Correct 57 ms 2324 KB Output is correct
5 Correct 84 ms 2388 KB Output is correct
6 Correct 78 ms 2212 KB Output is correct
7 Correct 78 ms 2384 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 464 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 365 ms 105500 KB Output is correct
12 Correct 393 ms 106072 KB Output is correct
13 Correct 411 ms 105332 KB Output is correct
14 Correct 398 ms 105296 KB Output is correct
15 Correct 353 ms 105864 KB Output is correct
16 Correct 406 ms 106336 KB Output is correct
17 Correct 419 ms 106536 KB Output is correct
18 Correct 355 ms 106384 KB Output is correct
19 Correct 359 ms 105596 KB Output is correct
20 Correct 392 ms 105748 KB Output is correct
21 Correct 364 ms 105784 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1064 ms 107052 KB Output is correct
2 Correct 224 ms 2248 KB Output is correct
3 Correct 230 ms 2216 KB Output is correct
4 Correct 246 ms 2328 KB Output is correct
5 Correct 247 ms 2384 KB Output is correct
6 Correct 217 ms 2200 KB Output is correct
7 Correct 243 ms 2292 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 344 KB Output is correct
11 Correct 1132 ms 105344 KB Output is correct
12 Correct 1154 ms 107004 KB Output is correct
13 Correct 1134 ms 105352 KB Output is correct
14 Correct 1104 ms 105336 KB Output is correct
15 Correct 1116 ms 106996 KB Output is correct
16 Correct 1120 ms 107104 KB Output is correct
17 Correct 1198 ms 106996 KB Output is correct
18 Correct 1118 ms 107028 KB Output is correct
19 Correct 1099 ms 106928 KB Output is correct
20 Correct 1121 ms 107008 KB Output is correct
21 Correct 1129 ms 106840 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 106180 KB Output is correct
2 Correct 80 ms 2184 KB Output is correct
3 Correct 76 ms 2108 KB Output is correct
4 Correct 57 ms 2324 KB Output is correct
5 Correct 84 ms 2388 KB Output is correct
6 Correct 78 ms 2212 KB Output is correct
7 Correct 78 ms 2384 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 464 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 365 ms 105500 KB Output is correct
12 Correct 393 ms 106072 KB Output is correct
13 Correct 411 ms 105332 KB Output is correct
14 Correct 398 ms 105296 KB Output is correct
15 Correct 353 ms 105864 KB Output is correct
16 Correct 406 ms 106336 KB Output is correct
17 Correct 419 ms 106536 KB Output is correct
18 Correct 355 ms 106384 KB Output is correct
19 Correct 359 ms 105596 KB Output is correct
20 Correct 392 ms 105748 KB Output is correct
21 Correct 364 ms 105784 KB Output is correct
22 Correct 1153 ms 106692 KB Output is correct
23 Correct 210 ms 2452 KB Output is correct
24 Correct 191 ms 2376 KB Output is correct
25 Correct 181 ms 2520 KB Output is correct
26 Correct 230 ms 2532 KB Output is correct
27 Correct 220 ms 2528 KB Output is correct
28 Correct 197 ms 2384 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 1201 ms 105332 KB Output is correct
33 Correct 1165 ms 106592 KB Output is correct
34 Correct 1148 ms 105284 KB Output is correct
35 Correct 1101 ms 105332 KB Output is correct
36 Correct 741 ms 105280 KB Output is correct
37 Correct 740 ms 105300 KB Output is correct
38 Correct 750 ms 105420 KB Output is correct
39 Correct 1118 ms 106888 KB Output is correct
40 Correct 1144 ms 106988 KB Output is correct
41 Correct 1046 ms 107280 KB Output is correct
42 Correct 1172 ms 106688 KB Output is correct
43 Correct 1106 ms 106616 KB Output is correct
44 Correct 1115 ms 106660 KB Output is correct
45 Correct 1174 ms 106636 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1016 ms 106684 KB Output is correct
2 Correct 250 ms 2384 KB Output is correct
3 Correct 213 ms 2532 KB Output is correct
4 Correct 233 ms 2500 KB Output is correct
5 Correct 232 ms 2464 KB Output is correct
6 Correct 253 ms 2584 KB Output is correct
7 Correct 222 ms 2384 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 992 ms 106636 KB Output is correct
12 Correct 1004 ms 106452 KB Output is correct
13 Correct 1046 ms 106796 KB Output is correct
14 Correct 981 ms 106792 KB Output is correct
15 Correct 969 ms 106676 KB Output is correct
16 Correct 1016 ms 106460 KB Output is correct
17 Correct 1002 ms 106500 KB Output is correct
18 Correct 991 ms 106636 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 -