oj.uz

Submission #920531

# Submission time Handle Problem Language Result Execution time Memory
920531 2024-02-02T17:31:13 Z myst6 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 644 ms 83536 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 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 1 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 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 1 ms 348 KB Output is correct
7 Correct 5 ms 1372 KB Output is correct
8 Correct 5 ms 1372 KB Output is correct
9 Correct 5 ms 1372 KB Output is correct
10 Correct 6 ms 1372 KB Output is correct
11 Correct 5 ms 1372 KB Output is correct
12 Correct 5 ms 1624 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 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 1 ms 348 KB Output is correct
7 Correct 5 ms 1372 KB Output is correct
8 Correct 5 ms 1372 KB Output is correct
9 Correct 5 ms 1372 KB Output is correct
10 Correct 6 ms 1372 KB Output is correct
11 Correct 5 ms 1372 KB Output is correct
12 Correct 5 ms 1624 KB Output is correct
13 Correct 604 ms 81016 KB Output is correct
14 Correct 555 ms 83112 KB Output is correct
15 Correct 597 ms 83160 KB Output is correct
16 Correct 644 ms 83072 KB Output is correct
17 Correct 609 ms 82964 KB Output is correct
18 Correct 589 ms 83536 KB Output is correct