Submission #855063

#	Time	Username	Problem	Language	Result	Execution time	Memory
855063		NeroZein	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	0 ms	344 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

struct SegTree {
  struct node {
    long long lm, rm; 
    long long a[2][2] = {}; 
  }; 
  int n;
  vector<node> seg; 
  SegTree(const vector<long long>& v) {
    n = (int) v.size(); 
    seg.resize(2 * n - 1); 
    build(0, 0, n - 1, v); 
  }
  node merge(const node& lc, const node& rc) {
    node ret;
    ret.lm = lc.lm;
    ret.rm = lc.rm;
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        for (int k = 0; k < 2; ++k) {
          for (int l = 0; l < 2; ++l) {
            if (k != l || (lc.rm >= 0 && rc.lm >= 0) || (lc.rm <= 0 && rc.rm <= 0)) {
              ret.a[i][j] = max(ret.a[i][j], lc.a[i][k] + rc.a[l][j]);               
            }
          }
        }
      }
    }
    return ret;
  }
  void build(int nd, int l, int r, const vector<long long>& v) {
    if (l == r) {
      seg[nd].lm = seg[nd].rm = v[l];
      seg[nd].a[1][1] = abs(v[l]);
      return;
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    build(nd + 1, l, mid, v);
    build(rs, mid + 1, r, v); 
    seg[nd] = merge(seg[nd + 1], seg[rs]); 
  }
  void upd(int nd, int l, int r, int p, int v) {
    if (l == r) {
      seg[nd].lm = seg[nd].rm = v;
      seg[nd].a[1][1] = abs(v); 
      return;
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (p <= mid) {
      upd(nd + 1, l, mid, p, v);
    } else {
      upd(rs, mid + 1, r, p, v); 
    }
    seg[nd] = merge(seg[nd + 1], seg[rs]); 
  }
  void upd(int p, int v) {
    upd(0, 0, n - 1, p, v); 
  }
};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  vector<int> a(n); 
  for (int i = 0; i < n; ++i) {
    cin >> a[i]; 
  }
  vector<long long> d(n - 1);
  for (int i = 0; i < n - 1; ++i) {
    d[i] = a[i + 1] - a[i]; 
  }
  SegTree st(d); 
  while (q--) {
    int l, r, v;
    cin >> l >> r >> v; 
    --l, --r; 
    if (l > 0) {
      d[l - 1] += v;
      st.upd(l - 1, d[l - 1]); 
    }
    if (r < n - 1) {
      d[r] -= v; 
      st.upd(r, d[r]); 
    }
    long long ans = 0;
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        ans = max(ans, st.seg[0].a[i][j]); 
      }
    }
    cout << ans << '\n';
  } 
  return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55