oj.uz

Submission #1017002

# Submission time Handle Problem Language Result Execution time Memory
1017002 2024-07-08T16:58:32 Z MilosMilutinovic Progression (NOI20_progression) C++14
68 / 100
 1092 ms 236112 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;
    long long sum_set;
    long long coeff_set;
    long long sum_add;
    long long coeff_add;
    Node(long long _sum = 0, long long _coeff = 0) : sum(_sum), coeff(_coeff) {
      sum_set = coeff_set = inf;
      sum_add = coeff_add = 0;
    }
  };

  int n;
  Node st[8 * MAX];

  void Push(int id) {
    if (st[id].sum_set == inf) {
      st[id * 2].sum += st[id].sum_add;
      st[id * 2].coeff += st[id].coeff_add;
      st[id * 2 + 1].sum += st[id].sum_add;
      st[id * 2 + 1].coeff += st[id].coeff_add;
      st[id * 2].sum_add += st[id].sum_add;
      st[id * 2].coeff_add += st[id].coeff_add;
      st[id * 2 + 1].sum_add += st[id].sum_add;
      st[id * 2 + 1].coeff_add += st[id].coeff_add;
      st[id].sum_add = 0;
      st[id].coeff_add = 0;
    } else {
      st[id * 2].sum = st[id].sum_set + st[id].sum_add;
      st[id * 2].coeff = st[id].coeff_set + st[id].coeff_add;
      st[id * 2 + 1].sum = st[id].sum_set + st[id].sum_add;
      st[id * 2 + 1].coeff = st[id].coeff_set + st[id].coeff_add;
      st[id * 2].sum_set = st[id].sum_set;
      st[id * 2].coeff_set = st[id].coeff_set;
      st[id * 2 + 1].sum_set = st[id].sum_set;
      st[id * 2 + 1].coeff_set = st[id].coeff_set;
      st[id].sum_set = inf;
      st[id].coeff_set = inf;
      st[id].sum_add = 0;
      st[id].coeff_add = 0;
    }
  }

  void Add(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;
      st[id].sum_add += x;
      st[id].coeff_add += y;
      Push(id);
      return;
    }
    Push(id);
    int mid = (l + r) >> 1;
    if (rr <= mid) {
      Add(id * 2, l, mid, ll, rr, x, y);
    } else if (ll > mid) {
      Add(id * 2 + 1, mid + 1, r, ll, rr, x, y);
    } else {
      Add(id * 2, l, mid, ll, rr, x, y);
      Add(id * 2 + 1, mid + 1, r, ll, rr, x, y);
    }
    st[id].sum = st[id * 2].sum + st[id * 2 + 1].sum;
    st[id].coeff = st[id * 2].coeff + st[id * 2 + 1].coeff;
  }

  void Set(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;
      st[id].sum_set = x;
      st[id].coeff_set = y;
      st[id].sum_add = 0;
      st[id].coeff_add = 0;
      Push(id);
      return;
    }
    Push(id);
    int mid = (l + r) >> 1;
    if (rr <= mid) {
      Set(id * 2, l, mid, ll, rr, x, y);
    } else if (ll > mid) {
      Set(id * 2 + 1, mid + 1, r, ll, rr, x, y);
    } else {
      Set(id * 2, l, mid, ll, rr, x, y);
      Set(id * 2 + 1, mid + 1, r, ll, rr, x, y);
    }
    st[id].sum = st[id * 2].sum + st[id * 2 + 1].sum;
    st[id].coeff = st[id * 2].coeff + st[id * 2 + 1].coeff;
  }

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

  long long Get(int i) {
    return Query(1, 0, n - 1, 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.Set(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.Add(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 - 1) - val.Get(l));
      } 
      if (r + 1 < n) {
        st.Set(1, 0, n - 1, r, r, val.Get(r) - val.Get(r + 1));
      } 
    }
    if (op == 2) {
      int l, r, s, c;
      cin >> l >> r >> s >> c;
      --l; --r;
      val.Set(1, 0, n - 1, l, r, s - c * 1LL * l, c);
      if (l < r) {
        st.Set(1, 0, n - 1, l, r - 1, -c);
      }
      if (l > 0) {
        st.Set(1, 0, n - 1, l - 1, l - 1, val.Get(l - 1) - val.Get(l));
      } 
      if (r + 1 < n) {
        st.Set(1, 0, n - 1, r, r, val.Get(r) - val.Get(r + 1));
      } 
    }
    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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 229460 KB Output is correct
2 Correct 129 ms 229108 KB Output is correct
3 Correct 132 ms 229200 KB Output is correct
4 Correct 130 ms 229284 KB Output is correct
5 Correct 133 ms 229204 KB Output is correct
6 Correct 141 ms 229412 KB Output is correct
7 Correct 129 ms 229200 KB Output is correct
8 Correct 56 ms 226112 KB Output is correct
9 Correct 55 ms 225872 KB Output is correct
10 Correct 55 ms 226028 KB Output is correct
11 Correct 468 ms 234576 KB Output is correct
12 Correct 484 ms 234580 KB Output is correct
13 Correct 483 ms 234736 KB Output is correct
14 Correct 474 ms 234832 KB Output is correct
15 Correct 466 ms 234820 KB Output is correct
16 Correct 545 ms 234556 KB Output is correct
17 Correct 475 ms 234668 KB Output is correct
18 Correct 471 ms 234580 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 225876 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 504 ms 226908 KB Output is correct
2 Correct 117 ms 226640 KB Output is correct
3 Correct 113 ms 226644 KB Output is correct
4 Correct 110 ms 226644 KB Output is correct
5 Correct 115 ms 226644 KB Output is correct
6 Correct 151 ms 226640 KB Output is correct
7 Correct 122 ms 226640 KB Output is correct
8 Correct 55 ms 225872 KB Output is correct
9 Correct 58 ms 225876 KB Output is correct
10 Correct 57 ms 225876 KB Output is correct
11 Correct 514 ms 226812 KB Output is correct
12 Correct 503 ms 227016 KB Output is correct
13 Correct 542 ms 226900 KB Output is correct
14 Correct 474 ms 226900 KB Output is correct
15 Correct 515 ms 226896 KB Output is correct
16 Correct 494 ms 227376 KB Output is correct
17 Correct 488 ms 227388 KB Output is correct
18 Correct 514 ms 227404 KB Output is correct
19 Correct 477 ms 226640 KB Output is correct
20 Correct 470 ms 226644 KB Output is correct
21 Correct 466 ms 226612 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 982 ms 230536 KB Output is correct
2 Correct 172 ms 229204 KB Output is correct
3 Correct 174 ms 229340 KB Output is correct
4 Correct 166 ms 229204 KB Output is correct
5 Correct 171 ms 229440 KB Output is correct
6 Correct 181 ms 229456 KB Output is correct
7 Correct 174 ms 229364 KB Output is correct
8 Correct 55 ms 226096 KB Output is correct
9 Correct 55 ms 225980 KB Output is correct
10 Correct 56 ms 226040 KB Output is correct
11 Correct 864 ms 232524 KB Output is correct
12 Correct 877 ms 235860 KB Output is correct
13 Correct 887 ms 232528 KB Output is correct
14 Correct 873 ms 232476 KB Output is correct
15 Correct 853 ms 235684 KB Output is correct
16 Correct 881 ms 235860 KB Output is correct
17 Correct 885 ms 235808 KB Output is correct
18 Correct 896 ms 236112 KB Output is correct
19 Correct 883 ms 235944 KB Output is correct
20 Correct 859 ms 235856 KB Output is correct
21 Correct 810 ms 235888 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 226908 KB Output is correct
2 Correct 117 ms 226640 KB Output is correct
3 Correct 113 ms 226644 KB Output is correct
4 Correct 110 ms 226644 KB Output is correct
5 Correct 115 ms 226644 KB Output is correct
6 Correct 151 ms 226640 KB Output is correct
7 Correct 122 ms 226640 KB Output is correct
8 Correct 55 ms 225872 KB Output is correct
9 Correct 58 ms 225876 KB Output is correct
10 Correct 57 ms 225876 KB Output is correct
11 Correct 514 ms 226812 KB Output is correct
12 Correct 503 ms 227016 KB Output is correct
13 Correct 542 ms 226900 KB Output is correct
14 Correct 474 ms 226900 KB Output is correct
15 Correct 515 ms 226896 KB Output is correct
16 Correct 494 ms 227376 KB Output is correct
17 Correct 488 ms 227388 KB Output is correct
18 Correct 514 ms 227404 KB Output is correct
19 Correct 477 ms 226640 KB Output is correct
20 Correct 470 ms 226644 KB Output is correct
21 Correct 466 ms 226612 KB Output is correct
22 Correct 939 ms 231252 KB Output is correct
23 Correct 151 ms 228172 KB Output is correct
24 Correct 192 ms 228176 KB Output is correct
25 Correct 179 ms 228176 KB Output is correct
26 Correct 235 ms 228100 KB Output is correct
27 Correct 203 ms 228188 KB Output is correct
28 Correct 179 ms 228168 KB Output is correct
29 Correct 64 ms 225924 KB Output is correct
30 Correct 62 ms 225888 KB Output is correct
31 Correct 64 ms 225876 KB Output is correct
32 Correct 1038 ms 229784 KB Output is correct
33 Correct 1060 ms 231092 KB Output is correct
34 Correct 1092 ms 229716 KB Output is correct
35 Correct 1050 ms 229968 KB Output is correct
36 Correct 833 ms 229688 KB Output is correct
37 Correct 848 ms 229668 KB Output is correct
38 Correct 843 ms 229652 KB Output is correct
39 Correct 1091 ms 230976 KB Output is correct
40 Correct 1064 ms 231208 KB Output is correct
41 Correct 1081 ms 231400 KB Output is correct
42 Correct 1061 ms 231052 KB Output is correct
43 Correct 1071 ms 230852 KB Output is correct
44 Correct 1008 ms 230992 KB Output is correct
45 Correct 981 ms 230872 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 229460 KB Output is correct
2 Correct 129 ms 229108 KB Output is correct
3 Correct 132 ms 229200 KB Output is correct
4 Correct 130 ms 229284 KB Output is correct
5 Correct 133 ms 229204 KB Output is correct
6 Correct 141 ms 229412 KB Output is correct
7 Correct 129 ms 229200 KB Output is correct
8 Correct 56 ms 226112 KB Output is correct
9 Correct 55 ms 225872 KB Output is correct
10 Correct 55 ms 226028 KB Output is correct
11 Correct 468 ms 234576 KB Output is correct
12 Correct 484 ms 234580 KB Output is correct
13 Correct 483 ms 234736 KB Output is correct
14 Correct 474 ms 234832 KB Output is correct
15 Correct 466 ms 234820 KB Output is correct
16 Correct 545 ms 234556 KB Output is correct
17 Correct 475 ms 234668 KB Output is correct
18 Correct 471 ms 234580 KB Output is correct
19 Incorrect 58 ms 225876 KB Output isn't correct
20 Halted 0 ms 0 KB -