oj.uz

Submission #587916

# Submission time Handle Problem Language Result Execution time Memory
587916 2022-07-02T14:00:35 Z MilosMilutinovic Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 595 ms 36220 KB 
/**
 *    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

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.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5 ms 852 KB Output is correct
8 Correct 5 ms 856 KB Output is correct
9 Correct 5 ms 852 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 7 ms 852 KB Output is correct
12 Correct 4 ms 852 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5 ms 852 KB Output is correct
8 Correct 5 ms 856 KB Output is correct
9 Correct 5 ms 852 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 7 ms 852 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 595 ms 35648 KB Output is correct
14 Correct 589 ms 35664 KB Output is correct
15 Correct 516 ms 35580 KB Output is correct
16 Correct 526 ms 35608 KB Output is correct
17 Correct 543 ms 35424 KB Output is correct
18 Correct 486 ms 36220 KB Output is correct