oj.uz

Submission #448742

# Submission time Handle Problem Language Result Execution time Memory
448742 2021-08-01T09:13:40 Z anayk Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 1559 ms 41416 KB 
#include <iostream>
#include <vector>

#define int long long

#define left (id+1)
#define mid ((l+r)/2)
#define right (id+2*(mid-l+1))

const int INF = 1'000'000'000'000'000;

struct node
{
  int val[3][3];

  void add(int v) {
    for(int i = 0; i < 3; i++) {
      val[0][i] -= v;
      val[2][i] += v;
      val[i][0] -= v;
      val[i][2] += v;
    }
  }
};

node empty = {{{-INF, 0, -INF}, {0, 0, 0}, {-INF, 0, -INF}}};

node get(int x) {
  node next = empty;
  next.val[0][1] = next.val[1][0] = -x;
  next.val[2][1] = next.val[1][2] = x;
  return next;
}

node merge(node &a, node &b) {
  node next;
  for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
      next.val[i][j] = std::max(a.val[i][j], b.val[i][j]);
      for(int k = 0; k < 3; k++)
        next.val[i][j] = std::max(next.val[i][j], a.val[i][k] + b.val[2-k][j]);
    }
  }
  return next;
}

int n;

struct seg
{
  std::vector<node> arr;
  std::vector<int> lazy;

  void push(int id, int l, int r) {
    if(lazy[id]) {
      arr[left].add(lazy[id]);
      arr[right].add(lazy[id]);
      lazy[left] += lazy[id];
      lazy[right] += lazy[id];
      lazy[id] = 0;
    }
  }

  void update(int x, int y, int v, int id = 0, int l = 0, int r = n-1) {
    if(y < l || r < x)
      return;

    if(x <= l && r <= y) {
      lazy[id] += v;
      arr[id].add(v);
      return;
    }

    push(id, l, r);
    update(x, y, v, left, l, mid);
    update(x, y, v, right, mid+1, r);

    arr[id]  = merge(arr[left], arr[right]);
  }
};

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  int q;
  std::cin >> n >> q;

  seg tree;
  tree.arr = std::vector<node>(2*n-1, empty);
  tree.lazy = std::vector<int>(2*n-1, 0);

  for(int i = 0; i < n; i++) {
    int x;
    std::cin >> x;

    tree.update(i, i, x);
  }

  while(q--) {
    int l, r, v;
    std::cin >> l >> r >> v;
    l--; r--;
    tree.update(l, r, v);

    std::cout << tree.arr[0].val[1][1] << std::endl;
  }

  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 14 ms 916 KB Output is correct
8 Correct 14 ms 844 KB Output is correct
9 Correct 17 ms 884 KB Output is correct
10 Correct 13 ms 888 KB Output is correct
11 Correct 14 ms 920 KB Output is correct
12 Correct 13 ms 920 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 14 ms 916 KB Output is correct
8 Correct 14 ms 844 KB Output is correct
9 Correct 17 ms 884 KB Output is correct
10 Correct 13 ms 888 KB Output is correct
11 Correct 14 ms 920 KB Output is correct
12 Correct 13 ms 920 KB Output is correct
13 Correct 1559 ms 40740 KB Output is correct
14 Correct 1468 ms 40672 KB Output is correct
15 Correct 1507 ms 40672 KB Output is correct
16 Correct 1443 ms 40704 KB Output is correct
17 Correct 1448 ms 40592 KB Output is correct
18 Correct 1466 ms 41416 KB Output is correct