oj.uz

Submission #1016927

# Submission time Handle Problem Language Result Execution time Memory
1016927 2024-07-08T15:41:19 Z MilosMilutinovic Progression (NOI20_progression) C++14
35 / 100
 3000 ms 306528 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX = 300300;
const long long inf = (long long) 1e18;

struct Value { 
  struct Node {
    long long sum;
    long long coeff;
    Node(long long _sum = 0, long long _coeff = 0) : sum(_sum), coeff(_coeff) {}
  };

  int n;
  Node st[8 * MAX];

  void Modify(int id, int l, int r, int ll, int rr, long long x, long long y) {
    if (ll <= l && r <= rr) {
      st[id].sum += x;
      st[id].coeff += y;
      return;
    }
    int mid = (l + r) >> 1;
    if (rr <= mid) {
      Modify(id * 2, l, mid, ll, rr, x, y);
    } else if (ll > mid) {
      Modify(id * 2 + 1, mid + 1, r, ll, rr, x, y);
    } else {
      Modify(id * 2, l, mid, ll, rr, x, y);
      Modify(id * 2 + 1, mid + 1, r, ll, rr, x, y);
    }
  }

  Node Query(int id, int l, int r, int p) {
    if (l == r) {
      return st[id];
    }
    int mid = (l + r) >> 1;
    Node nd;
    if (p <= mid) {
      nd = Query(id * 2, l, mid, p);
    } else {
      nd = Query(id * 2 + 1, mid + 1, r, p);
    }
    return {st[id].sum + nd.sum, st[id].coeff + nd.coeff};
  }

  long long Get(int i) {
    Node nd = Query(1, 0, n - 1, i); 
    return nd.sum + nd.coeff * i;
  }
} val;

struct Solver {
  struct Node {
    int len;
    int mx;
    int mx_l;
    int mx_r;
    long long val_l;
    long long val_r;
    long long lzy_add;
    long long lzy_set;
    Node() {
      lzy_set = inf;
      lzy_add = 0;
    }
  };

  Node Merge(Node a, Node b) {
    Node nd;
    nd.len = a.len + b.len;
    nd.mx = max(a.mx, b.mx);
    nd.mx_l = a.mx_l;
    nd.mx_r = b.mx_r;
    if (a.val_r == b.val_l) {
      nd.mx = max(nd.mx, a.mx_r + b.mx_l);
      if (a.mx_l == a.len) {
        nd.mx_l = max(nd.mx_l, a.len + b.mx_l);
      }
      if (b.mx_r == b.len) {
        nd.mx_r = max(nd.mx_r, a.mx_r + b.len);
      }
    }
    nd.val_l = a.val_l;
    nd.val_r = b.val_r;
    return nd;
  }

  Node st[8 * MAX];

  void Push(int id) {
    if (st[id].lzy_set == inf) {
      st[id * 2].val_l += st[id].lzy_add;
      st[id * 2].val_r += st[id].lzy_add;
      st[id * 2 + 1].val_l += st[id].lzy_add;
      st[id * 2 + 1].val_r += st[id].lzy_add;
      st[id * 2].lzy_add += st[id].lzy_add;
      st[id * 2 + 1].lzy_add += st[id].lzy_add;
      st[id].lzy_add = 0;
    } else {
      st[id * 2].val_l = st[id].lzy_set + st[id].lzy_add;
      st[id * 2].val_r = st[id].lzy_set + st[id].lzy_add;
      st[id * 2 + 1].val_l = st[id].lzy_set + st[id].lzy_add;
      st[id * 2 + 1].val_r = st[id].lzy_set + st[id].lzy_add;
      st[id * 2].lzy_set = st[id].lzy_set;
      st[id * 2].lzy_add = st[id].lzy_add;
      st[id * 2 + 1].lzy_set = st[id].lzy_set;
      st[id * 2 + 1].lzy_add = st[id].lzy_add;
      st[id * 2].mx = st[id * 2].mx_l = st[id * 2].mx_r = st[id * 2].len;
      st[id * 2 + 1].mx = st[id * 2 + 1].mx_l = st[id * 2 + 1].mx_r = st[id * 2 + 1].len;
      st[id].lzy_set = inf;
      st[id].lzy_add = 0;
    }
  }

  void Build(int id, int l, int r) {
    if (l == r) {    
      st[id].val_l = st[id].val_r = 0;
      st[id].len = 1;
      st[id].mx = st[id].mx_l = st[id].mx_r = 1;
      return;
    }
    int mid = (l + r) >> 1;
    Build(id * 2, l, mid);
    Build(id * 2 + 1, mid + 1, r);
    st[id] = Merge(st[id * 2], st[id * 2 + 1]);
  }

  void Set(int id, int l, int r, int ll, int rr, long long x) {
    if (ll <= l && r <= rr) {
      st[id].mx = st[id].mx_l = st[id].mx_r = st[id].len;
      st[id].val_l = x;
      st[id].val_r = x;
      st[id].lzy_set = x;
      st[id].lzy_add = 0;
      Push(id);
      return;
    }
    Push(id);
    int mid = (l + r) >> 1;
    if (rr <= mid) {
      Set(id * 2, l, mid, ll, rr, x);
    } else if (ll > mid) {
      Set(id * 2 + 1, mid + 1, r, ll, rr, x);
    } else {
      Set(id * 2, l, mid, ll, rr, x);
      Set(id * 2 + 1, mid + 1, r, ll, rr, x);
    }
    st[id] = Merge(st[id * 2], st[id * 2 + 1]);
  }

  void Add(int id, int l, int r, int ll, int rr, long long x) {
    if (ll <= l && r <= rr) {
      st[id].val_l += x;
      st[id].val_r += x;
      st[id].lzy_add += x;
      Push(id);
      return;
    }
    Push(id);
    int mid = (l + r) >> 1;
    if (rr <= mid) {
      Add(id * 2, l, mid, ll, rr, x);
    } else if (ll > mid) {
      Add(id * 2 + 1, mid + 1, r, ll, rr, x);
    } else {
      Add(id * 2, l, mid, ll, rr, x);
      Add(id * 2 + 1, mid + 1, r, ll, rr, x);
    }
    st[id] = Merge(st[id * 2], st[id * 2 + 1]);
  }

  Node Query(int id, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return st[id];
    }
    Push(id);
    int mid = (l + r) >> 1;
    Node ret;
    if (rr <= mid) {
      ret = Query(id * 2, l, mid, ll, rr);
    } else if (ll > mid) {
      ret = Query(id * 2 + 1, mid + 1, r, ll, rr);
    } else {
      ret = Merge(Query(id * 2, l, mid, ll, rr), Query(id * 2 + 1, mid + 1, r, ll, rr));
    }
    st[id] = Merge(st[id * 2], st[id * 2 + 1]);
    return ret;
  }
} st;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    int d;
    cin >> d;
    val.Modify(1, 0, n - 1, i, i, d, 0);
  }
  val.n = n;
  st.Build(1, 0, n - 1);
  for (int i = 0; i + 1 < n; i++) {
    st.Set(1, 0, n - 1, i, i, val.Get(i) - val.Get(i + 1));
  }
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int l, r, s, c;
      cin >> l >> r >> s >> c;
      --l; --r;
      val.Modify(1, 0, n - 1, l, r, s - c * 1LL * l, c);
      if (l < r) {
        st.Add(1, 0, n - 1, l, r - 1, -c);
      } 
      if (l > 0) {
        st.Set(1, 0, n - 1, l - 1, l - 1, val.Get(l) - val.Get(l + 1));
      } 
      if (r + 1 < n) {
        st.Set(1, 0, n - 1, r, r, val.Get(r) - val.Get(r + 1));
      } 
    }
    if (op == 2) {

    }
    if (op == 3) {
      int l, r;
      cin >> l >> r;
      --l; --r;
      if (l == r) {
        cout << 1 << '\n';
      } else {
        cout << st.Query(1, 0, n - 1, l, r - 1).mx + 1 << '\n';
      }
    }
  }
  return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 151892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 150864 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 342 ms 151904 KB Output is correct
2 Correct 81 ms 151380 KB Output is correct
3 Correct 84 ms 151376 KB Output is correct
4 Correct 69 ms 151248 KB Output is correct
5 Correct 76 ms 151520 KB Output is correct
6 Correct 78 ms 151416 KB Output is correct
7 Correct 76 ms 151376 KB Output is correct
8 Correct 19 ms 150876 KB Output is correct
9 Correct 19 ms 150868 KB Output is correct
10 Correct 19 ms 150872 KB Output is correct
11 Correct 323 ms 151636 KB Output is correct
12 Correct 324 ms 151904 KB Output is correct
13 Correct 320 ms 151516 KB Output is correct
14 Correct 334 ms 151656 KB Output is correct
15 Correct 380 ms 151904 KB Output is correct
16 Correct 340 ms 152160 KB Output is correct
17 Correct 358 ms 152136 KB Output is correct
18 Correct 337 ms 152164 KB Output is correct
19 Correct 305 ms 151376 KB Output is correct
20 Correct 365 ms 151632 KB Output is correct
21 Correct 306 ms 151408 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 363 ms 306528 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 151904 KB Output is correct
2 Correct 81 ms 151380 KB Output is correct
3 Correct 84 ms 151376 KB Output is correct
4 Correct 69 ms 151248 KB Output is correct
5 Correct 76 ms 151520 KB Output is correct
6 Correct 78 ms 151416 KB Output is correct
7 Correct 76 ms 151376 KB Output is correct
8 Correct 19 ms 150876 KB Output is correct
9 Correct 19 ms 150868 KB Output is correct
10 Correct 19 ms 150872 KB Output is correct
11 Correct 323 ms 151636 KB Output is correct
12 Correct 324 ms 151904 KB Output is correct
13 Correct 320 ms 151516 KB Output is correct
14 Correct 334 ms 151656 KB Output is correct
15 Correct 380 ms 151904 KB Output is correct
16 Correct 340 ms 152160 KB Output is correct
17 Correct 358 ms 152136 KB Output is correct
18 Correct 337 ms 152164 KB Output is correct
19 Correct 305 ms 151376 KB Output is correct
20 Correct 365 ms 151632 KB Output is correct
21 Correct 306 ms 151408 KB Output is correct
22 Incorrect 690 ms 156840 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 151892 KB Time limit exceeded
2 Halted 0 ms 0 KB -