oj.uz

Submission #855068

# Submission time Handle Problem Language Result Execution time Memory
855068 2023-09-30T03:38:46 Z NeroZein Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 515 ms 31308 KB 
#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 = rc.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.lm <= 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, long long 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, long long 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
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 6 ms 860 KB Output is correct
8 Correct 5 ms 860 KB Output is correct
9 Correct 5 ms 860 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 5 ms 1112 KB Output is correct
12 Correct 4 ms 860 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 6 ms 860 KB Output is correct
8 Correct 5 ms 860 KB Output is correct
9 Correct 5 ms 860 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 5 ms 1112 KB Output is correct
12 Correct 4 ms 860 KB Output is correct
13 Correct 515 ms 30948 KB Output is correct
14 Correct 503 ms 30740 KB Output is correct
15 Correct 503 ms 30500 KB Output is correct
16 Correct 500 ms 30584 KB Output is correct
17 Correct 497 ms 30700 KB Output is correct
18 Correct 435 ms 31308 KB Output is correct