Submission #448742

#	Time	Username	Problem	Language	Result	Execution time	Memory
448742		anayk	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	1559 ms	41416 KiB

Main

#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 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55