oj.uz

Submission #1016918

# Submission time Handle Problem Language Result Execution time Memory
1016918 2024-07-08T15:31:32 Z MilosMilutinovic Progression (NOI20_progression) C++14
35 / 100
 351 ms 257612 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;
  };

  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].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) {

    }
    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 Incorrect 188 ms 125776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 113240 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 336 ms 126548 KB Output is correct
2 Correct 79 ms 115792 KB Output is correct
3 Correct 76 ms 115736 KB Output is correct
4 Correct 68 ms 115848 KB Output is correct
5 Correct 75 ms 116060 KB Output is correct
6 Correct 76 ms 115924 KB Output is correct
7 Correct 77 ms 116096 KB Output is correct
8 Correct 17 ms 113244 KB Output is correct
9 Correct 17 ms 113244 KB Output is correct
10 Correct 17 ms 113244 KB Output is correct
11 Correct 338 ms 131176 KB Output is correct
12 Correct 351 ms 132704 KB Output is correct
13 Correct 347 ms 131296 KB Output is correct
14 Correct 323 ms 131320 KB Output is correct
15 Correct 349 ms 132668 KB Output is correct
16 Correct 330 ms 133044 KB Output is correct
17 Correct 334 ms 133004 KB Output is correct
18 Correct 334 ms 133308 KB Output is correct
19 Correct 306 ms 132544 KB Output is correct
20 Correct 313 ms 132436 KB Output is correct
21 Correct 315 ms 132632 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 126548 KB Output is correct
2 Correct 79 ms 115792 KB Output is correct
3 Correct 76 ms 115736 KB Output is correct
4 Correct 68 ms 115848 KB Output is correct
5 Correct 75 ms 116060 KB Output is correct
6 Correct 76 ms 115924 KB Output is correct
7 Correct 77 ms 116096 KB Output is correct
8 Correct 17 ms 113244 KB Output is correct
9 Correct 17 ms 113244 KB Output is correct
10 Correct 17 ms 113244 KB Output is correct
11 Correct 338 ms 131176 KB Output is correct
12 Correct 351 ms 132704 KB Output is correct
13 Correct 347 ms 131296 KB Output is correct
14 Correct 323 ms 131320 KB Output is correct
15 Correct 349 ms 132668 KB Output is correct
16 Correct 330 ms 133044 KB Output is correct
17 Correct 334 ms 133004 KB Output is correct
18 Correct 334 ms 133308 KB Output is correct
19 Correct 306 ms 132544 KB Output is correct
20 Correct 313 ms 132436 KB Output is correct
21 Correct 315 ms 132632 KB Output is correct
22 Runtime error 260 ms 257612 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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