oj.uz

Submission #1029868

# Submission time Handle Problem Language Result Execution time Memory
1029868 2024-07-21T12:50:48 Z avighna Progression (NOI20_progression) C++17
35 / 100
 263 ms 64336 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;
      // if (l != r) {
      //   tree.update(l, s);
      //   tree.update(l + 1, c - s);
      //   tree.update(r + 1, -c - (r - l) * c - s);
      //   if (r + 2 <= n) {
      //     tree.update(r + 2, (r - l) * c + s);
      //   }
      // } else {

      // }
    } 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 189 ms 62776 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 251 ms 61520 KB Output is correct
2 Correct 71 ms 3156 KB Output is correct
3 Correct 84 ms 2896 KB Output is correct
4 Correct 45 ms 3084 KB Output is correct
5 Correct 81 ms 3168 KB Output is correct
6 Correct 74 ms 3156 KB Output is correct
7 Correct 76 ms 3264 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 228 ms 60076 KB Output is correct
12 Correct 243 ms 61548 KB Output is correct
13 Correct 237 ms 59988 KB Output is correct
14 Correct 253 ms 60256 KB Output is correct
15 Correct 236 ms 61360 KB Output is correct
16 Correct 263 ms 62040 KB Output is correct
17 Correct 254 ms 61992 KB Output is correct
18 Correct 256 ms 62036 KB Output is correct
19 Correct 214 ms 61268 KB Output is correct
20 Correct 225 ms 61244 KB Output is correct
21 Correct 242 ms 61488 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 61520 KB Output is correct
2 Correct 71 ms 3156 KB Output is correct
3 Correct 84 ms 2896 KB Output is correct
4 Correct 45 ms 3084 KB Output is correct
5 Correct 81 ms 3168 KB Output is correct
6 Correct 74 ms 3156 KB Output is correct
7 Correct 76 ms 3264 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 228 ms 60076 KB Output is correct
12 Correct 243 ms 61548 KB Output is correct
13 Correct 237 ms 59988 KB Output is correct
14 Correct 253 ms 60256 KB Output is correct
15 Correct 236 ms 61360 KB Output is correct
16 Correct 263 ms 62040 KB Output is correct
17 Correct 254 ms 61992 KB Output is correct
18 Correct 256 ms 62036 KB Output is correct
19 Correct 214 ms 61268 KB Output is correct
20 Correct 225 ms 61244 KB Output is correct
21 Correct 242 ms 61488 KB Output is correct
22 Incorrect 208 ms 63828 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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