oj.uz

Submission #1029870

# Submission time Handle Problem Language Result Execution time Memory
1029870 2024-07-21T12:53:38 Z avighna Progression (NOI20_progression) C++17
48 / 100
 662 ms 63828 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;
  ll n;

  SegmentTree(ll n) {
    this->n = n;
    seg.resize(4 * 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]);
  }

  Node query(ll v, ll tl, ll tr, ll l, ll r) {
    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) {
    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); }
};

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);
  tree.construct(diff_diff, 1, 0, n);
  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;
      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);
        }
      }
    } else if (t == 2) {
      ll s, c;
      std::cin >> 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 425 ms 59220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 58704 KB Output is correct
2 Correct 102 ms 2384 KB Output is correct
3 Correct 62 ms 2132 KB Output is correct
4 Correct 46 ms 2128 KB Output is correct
5 Correct 78 ms 2388 KB Output is correct
6 Correct 77 ms 2260 KB Output is correct
7 Correct 75 ms 2384 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 247 ms 57996 KB Output is correct
12 Correct 247 ms 58692 KB Output is correct
13 Correct 244 ms 57880 KB Output is correct
14 Correct 244 ms 57936 KB Output is correct
15 Correct 249 ms 58792 KB Output is correct
16 Correct 257 ms 59040 KB Output is correct
17 Correct 279 ms 58964 KB Output is correct
18 Correct 281 ms 59444 KB Output is correct
19 Correct 225 ms 58432 KB Output is correct
20 Correct 226 ms 58348 KB Output is correct
21 Correct 215 ms 58276 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 368 ms 59752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 58704 KB Output is correct
2 Correct 102 ms 2384 KB Output is correct
3 Correct 62 ms 2132 KB Output is correct
4 Correct 46 ms 2128 KB Output is correct
5 Correct 78 ms 2388 KB Output is correct
6 Correct 77 ms 2260 KB Output is correct
7 Correct 75 ms 2384 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 247 ms 57996 KB Output is correct
12 Correct 247 ms 58692 KB Output is correct
13 Correct 244 ms 57880 KB Output is correct
14 Correct 244 ms 57936 KB Output is correct
15 Correct 249 ms 58792 KB Output is correct
16 Correct 257 ms 59040 KB Output is correct
17 Correct 279 ms 58964 KB Output is correct
18 Correct 281 ms 59444 KB Output is correct
19 Correct 225 ms 58432 KB Output is correct
20 Correct 226 ms 58348 KB Output is correct
21 Correct 215 ms 58276 KB Output is correct
22 Correct 650 ms 59408 KB Output is correct
23 Correct 159 ms 3668 KB Output is correct
24 Correct 151 ms 3668 KB Output is correct
25 Correct 150 ms 3668 KB Output is correct
26 Correct 159 ms 3496 KB Output is correct
27 Correct 206 ms 3668 KB Output is correct
28 Correct 156 ms 3460 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 596 KB Output is correct
32 Correct 625 ms 60940 KB Output is correct
33 Correct 605 ms 63620 KB Output is correct
34 Correct 662 ms 61012 KB Output is correct
35 Correct 657 ms 60860 KB Output is correct
36 Correct 502 ms 60756 KB Output is correct
37 Correct 495 ms 60636 KB Output is correct
38 Correct 529 ms 60860 KB Output is correct
39 Correct 616 ms 63760 KB Output is correct
40 Correct 619 ms 63828 KB Output is correct
41 Correct 647 ms 63644 KB Output is correct
42 Correct 625 ms 63572 KB Output is correct
43 Correct 604 ms 63572 KB Output is correct
44 Correct 601 ms 63540 KB Output is correct
45 Correct 593 ms 63532 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 425 ms 59220 KB Output isn't correct
2 Halted 0 ms 0 KB -