Submission #587916

#	Time	Username	Problem	Language	Result	Execution time	Memory
587916		MilosMilutinovic	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	595 ms	36220 KiB

Main

/**
 *    author:  wxhtzdy
 *    created: 02.07.2022 15:37:43
**/
#include <bits/stdc++.h>

using namespace std;

struct node {
  long long dp[2][2];
  long long L, R;
};

const int MAX = 200000;
const long long inf = 1e10;

long long a[MAX];
node st[4 * MAX];

int sgn(long long x) {
  return (x < 0 ? -1 : (x == 0 ? 0 : 1));
}

node merge(node l, node r) {
  node ret;
  ret.L = l.L;
  ret.R = r.R;
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      ret.dp[i][j] = -inf;
    }
  }
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      if (i == 1 && j == 1 && sgn(l.R) != sgn(r.L)) {
        continue;
      }
      for (int ii = 0; ii < 2; ii++) {
        for (int jj = 0; jj < 2; jj++) {
          ret.dp[ii][jj] = max(ret.dp[ii][jj], l.dp[ii][i] + r.dp[j][jj]);  
        }
      }
    }
  }
  return ret;
}
    
void build(int node, int l, int r) {
  if (l == r) {
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        st[node].dp[i][j] = -inf;
      }
    }
    st[node].dp[0][0] = 0;
    st[node].dp[1][1] = abs(a[l]);
    st[node].L = st[node].R = a[l];
    return;
  }
  int mid = l + r >> 1;
  build(node * 2, l, mid);
  build(node * 2 + 1, mid + 1, r);
  st[node] = merge(st[node * 2], st[node * 2 + 1]);
}

void update(int node, int l, int r, int i) {
  if (l == r) {
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        st[node].dp[i][j] = -inf;
      }
    }
    st[node].dp[0][0] = 0;
    st[node].dp[1][1] = abs(a[l]);
    st[node].L = st[node].R = a[l];
    return;
  }
  int mid = l + r >> 1;
  if (i <= mid) {
    update(node * 2, l, mid, i);
  } else {
    update(node * 2 + 1, mid + 1, r, i);
  }
  st[node] = merge(st[node * 2], st[node * 2 + 1]);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
   cin >> a[i];
  }
  for (int i = 0; i < n - 1; i++) {
    a[i] -= a[i + 1];
  }
  if (n > 1) {
    build(1, 0, n - 2);
  }
  while (q--) {
    int l, r, x;
    cin >> l >> r >> x;
    --l; --r;
    if (n == 1) {
      cout << 0 << '\n';
      continue;
    }
    if (l > 0) {
      a[l - 1] -= x;
      update(1, 0, n - 2, l - 1);
    }   
    a[r] += x;
    if (r < n - 1) {
      update(1, 0, n - 2, r);   
    }    
    long long ans = 0;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        ans = max(ans, st[1].dp[i][j]);
      }
    }
    cout << ans << '\n';
  }                                  
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:60:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'void update(int, int, int, int)':
Main.cpp:78:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |   int mid = l + r >> 1;
      |             ~~^~~

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