Submission #920531

#	Time	Username	Problem	Language	Result	Execution time	Memory
920531		myst6	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	644 ms	83536 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

// for an O(nq) solution:
// take multiple subsegments of the array, skipping element straight after
// 9 -2 3 -9 -5 -6 -7 -10 0 1 5 7 -10
// (9) - (-9 -5 -6 -7 -10) + (1 5 7)
// dp[0] => max when not taking last
// dp[1] => max score when taking last, and adding
// dp[2] => max score when taking last, and subbing
// can go from 0 => 0/1/2
//        from 1 => 1/0
//        from 2 => 2/0
// ndp[0] = max(dp[0], dp[1], dp[2])
// ndp[1] = max(dp[0], dp[1]) + diff[i]
// ndp[2] = max(dp[0], dp[2]) - diff[i]

// for a segment tree:
// each node stores dp[a][b] = max sum when left value ignored(0)/added(1)/subtracted(2)

using DP = array<array<int, 3>, 3>; 

struct Info {
  DP dp;
  Info(DP dp) { this->dp = dp; }
  Info() {
    for (int a=0; a<3; a++)
      for (int b=0; b<3; b++)
        dp[a][b] = 0;
  } 
  Info combine(Info &other) {
    Info res;
    for (int a=0; a<3; a++)
      for (int b=0; b<3; b++)
        res.dp[a][b] = max({
          dp[a][0] + max({other.dp[0][b], other.dp[1][b], other.dp[2][b]}),
          dp[a][1] + max({other.dp[0][b], other.dp[1][b]}),
          dp[a][2] + max({other.dp[0][b], other.dp[2][b]}),
        });
    return res;
  }
};

struct Tree {
  vector<Info> info;
  Tree(int size) { info.resize(size * 4); }
  void build(vector<Info> &base, int x, int xl, int xr) {
    if (xl == xr) {
      info[x] = base[xl];
    } else {
      int xm = (xl + xr) / 2;
      build(base, x*2, xl, xm);
      build(base, x*2+1, xm+1, xr);
      info[x] = info[x*2].combine(info[x*2+1]);
    }
  }
  void update(int v, int x, int xl, int xr, Info delta) {
    if (xl == xr) {
      info[x] = delta;
    } else {
      int xm = (xl + xr) / 2;
      if (v <= xm) update(v, x*2, xl, xm, delta);
      else update(v, x*2+1, xm+1, xr, delta);
      info[x] = info[x*2].combine(info[x*2+1]);
    }
  }
};

Info get(int diff) {
  Info res;
  res.dp[1][1] = diff;
  res.dp[2][2] = -diff;
  return res;
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  vector<int> A(n);
  for (int i=0; i<n; i++) cin >> A[i];
  vector<int> diff(n);
  for (int i=1; i<n; i++) diff[i] = A[i] - A[i-1];
  vector<Info> base(n);
  for (int i=1; i<n; i++) base[i] = get(diff[i]);
  Tree tree(n);
  tree.build(base, 1, 1, n-1);
  while (q--) {
    int l, r, x;
    cin >> l >> r >> x;
    if (l > 1) {
      diff[l-1] += x;
      tree.update(l-1, 1, 1, n-1, get(diff[l-1]));
    }
    if (r < n) {
      diff[r] -= x;
      tree.update(r, 1, 1, n-1, get(diff[r]));
    }
    int ans = 0;
    for (int a=0; a<3; a++) 
      for (int b=0; b<3; b++)
        ans = max(ans, tree.info[1].dp[a][b]);
    cout << ans << "\n";
  }
  return 0;
}

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