oj.uz

Submission #1017004

# Submission time Handle Problem Language Result Execution time Memory
1017004 2024-07-08T17:00:55 Z MilosMilutinovic Progression (NOI20_progression) C++14
61 / 100
 3000 ms 234368 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;
  vector<long long> f(n);
  for (int i = 0; i < n; i++) {
    int d;
    cin >> d;
    f[i] = 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, f[i] - f[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);
      for (int i = l; i <= r; i++) {
        f[i] += s + (i - l) * 1LL * 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, f[l - 1] - f[l]);
      } 
      if (r + 1 < n) {
        st.Set(1, 0, n - 1, r, r, f[r] - f[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);
      for (int i = l; i <= r; i++) {
        f[i] = s + (i - l) * 1LL * 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, f[l - 1] - f[l]);
      } 
      if (r + 1 < n) {
        st.Set(1, 0, n - 1, r, r, f[r] - f[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
0 / 9.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 226060 KB Output is correct
2 Correct 58 ms 225868 KB Output is correct
3 Correct 60 ms 225872 KB Output is correct
4 Correct 60 ms 225872 KB Output is correct
5 Correct 60 ms 225876 KB Output is correct
6 Correct 57 ms 225872 KB Output is correct
7 Correct 61 ms 226016 KB Output is correct
8 Correct 65 ms 225872 KB Output is correct
9 Correct 60 ms 225876 KB Output is correct
10 Correct 60 ms 226132 KB Output is correct
11 Correct 64 ms 226108 KB Output is correct
12 Correct 67 ms 226128 KB Output is correct
13 Correct 62 ms 225976 KB Output is correct
14 Correct 57 ms 225872 KB Output is correct
15 Correct 59 ms 226132 KB Output is correct
16 Correct 60 ms 226112 KB Output is correct
17 Correct 61 ms 226128 KB Output is correct
18 Correct 57 ms 226012 KB Output is correct
19 Correct 57 ms 226000 KB Output is correct
20 Correct 60 ms 225928 KB Output is correct
21 Correct 56 ms 225876 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 232788 KB Output is correct
2 Correct 133 ms 228104 KB Output is correct
3 Correct 116 ms 228216 KB Output is correct
4 Correct 112 ms 228180 KB Output is correct
5 Correct 116 ms 228236 KB Output is correct
6 Correct 114 ms 228288 KB Output is correct
7 Correct 117 ms 228168 KB Output is correct
8 Correct 57 ms 225876 KB Output is correct
9 Correct 57 ms 225876 KB Output is correct
10 Correct 56 ms 225876 KB Output is correct
11 Correct 392 ms 232020 KB Output is correct
12 Correct 435 ms 232792 KB Output is correct
13 Correct 394 ms 232056 KB Output is correct
14 Correct 386 ms 231840 KB Output is correct
15 Correct 390 ms 232784 KB Output is correct
16 Correct 394 ms 233360 KB Output is correct
17 Correct 411 ms 233216 KB Output is correct
18 Correct 384 ms 233280 KB Output is correct
19 Correct 373 ms 232616 KB Output is correct
20 Correct 380 ms 232544 KB Output is correct
21 Correct 367 ms 232528 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 234368 KB Output is correct
2 Correct 148 ms 228088 KB Output is correct
3 Correct 140 ms 227924 KB Output is correct
4 Correct 144 ms 228032 KB Output is correct
5 Correct 143 ms 227924 KB Output is correct
6 Correct 145 ms 227920 KB Output is correct
7 Correct 140 ms 228064 KB Output is correct
8 Correct 56 ms 225872 KB Output is correct
9 Correct 60 ms 226112 KB Output is correct
10 Correct 56 ms 225888 KB Output is correct
11 Correct 556 ms 231976 KB Output is correct
12 Correct 537 ms 233660 KB Output is correct
13 Correct 519 ms 232016 KB Output is correct
14 Correct 534 ms 232068 KB Output is correct
15 Correct 548 ms 233560 KB Output is correct
16 Correct 536 ms 233760 KB Output is correct
17 Correct 544 ms 233756 KB Output is correct
18 Correct 592 ms 233812 KB Output is correct
19 Correct 612 ms 233704 KB Output is correct
20 Correct 531 ms 233696 KB Output is correct
21 Correct 584 ms 233808 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 232788 KB Output is correct
2 Correct 133 ms 228104 KB Output is correct
3 Correct 116 ms 228216 KB Output is correct
4 Correct 112 ms 228180 KB Output is correct
5 Correct 116 ms 228236 KB Output is correct
6 Correct 114 ms 228288 KB Output is correct
7 Correct 117 ms 228168 KB Output is correct
8 Correct 57 ms 225876 KB Output is correct
9 Correct 57 ms 225876 KB Output is correct
10 Correct 56 ms 225876 KB Output is correct
11 Correct 392 ms 232020 KB Output is correct
12 Correct 435 ms 232792 KB Output is correct
13 Correct 394 ms 232056 KB Output is correct
14 Correct 386 ms 231840 KB Output is correct
15 Correct 390 ms 232784 KB Output is correct
16 Correct 394 ms 233360 KB Output is correct
17 Correct 411 ms 233216 KB Output is correct
18 Correct 384 ms 233280 KB Output is correct
19 Correct 373 ms 232616 KB Output is correct
20 Correct 380 ms 232544 KB Output is correct
21 Correct 367 ms 232528 KB Output is correct
22 Execution timed out 3042 ms 228696 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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