oj.uz

Submission #850181

# Submission time Handle Problem Language Result Execution time Memory
850181 2023-09-16T01:06:13 Z gun_gan Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 303 ms 38372 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 2e5 + 5;

int N, Q;
ll A[MX], B[MX];

struct segtree {

      struct node {
            ll lv = 0, rv = 0, dp[2][2] {}; // sign of left, sign of right, dp values;
            // 0 -> exclude , 1 -> include
      };

      node t[4 * MX];

      node merge(node a, node b) {

            if(!a.lv) return b;
            if(!b.lv) return a;

            node c;

            c.dp[0][0] = max(a.dp[0][1] + b.dp[0][0], a.dp[0][0] + b.dp[1][0]); 
            c.dp[0][1] = max(a.dp[0][1] + b.dp[0][1], a.dp[0][0] + b.dp[1][1]);
            c.dp[1][0] = max(a.dp[1][0] + b.dp[1][0], a.dp[1][1] + b.dp[0][0]);
            c.dp[1][1] = max(a.dp[1][1] + b.dp[0][1], a.dp[1][0] + b.dp[1][1]);

            if(a.rv == b.lv) {
                  c.dp[0][0] = max(c.dp[0][0], a.dp[0][1] + b.dp[1][0]);
                  c.dp[0][1] = max(c.dp[0][1], a.dp[0][1] + b.dp[1][1]);
                  c.dp[1][0] = max(c.dp[1][0], a.dp[1][1] + b.dp[1][0]);
                  c.dp[1][1] = max(c.dp[1][1], a.dp[1][1] + b.dp[1][1]);
            }

            c.lv = a.lv;
            c.rv = b.rv;

            return c;
      }

      void update(int v, int l, int r, int pos, int x) {
            if(r < pos || l > pos) return;
            if(l == r) {
                  B[l] += x;
                  t[v].dp[0][0] = 0;
                  t[v].dp[0][1] = 0;
                  t[v].dp[1][0] = 0;
                  t[v].dp[1][1] = abs(B[l]);
                  t[v].lv = B[l] >= 0 ? 1 : -1;
                  t[v].rv = B[l] >= 0 ? 1 : -1;
                  return;
            }
            int mid = (l + r) >> 1;
            update(v * 2 + 0, l, mid + 0, pos, x);
            update(v * 2 + 1, mid + 1, r, pos, x);
            t[v] = merge(t[v * 2 + 0], t[v * 2 + 1]);
      }

      void build(int v, int l, int r) {
            if(l == r) {
                  t[v].dp[0][0] = 0;
                  t[v].dp[0][1] = 0;
                  t[v].dp[1][0] = 0;
                  t[v].dp[1][1] = abs(B[l]);
                  t[v].lv = B[l] >= 0 ? 1 : -1;
                  t[v].rv = B[l] >= 0 ? 1 : -1;
                  return;
            }
            int mid = (l + r) >> 1;
            build(v * 2 + 0, l, mid + 0);
            build(v * 2 + 1, mid + 1, r);
            t[v] = merge(t[v * 2 + 0], t[v * 2 + 1]);
      }
} st;

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      cin >> N >> Q;

      for(int i = 1; i <= N; i++) 
            cin >> A[i];
      
      for(int i = 1; i < N; i++) 
            B[i] = A[i + 1] - A[i];

      st.build(1, 1, N - 1);

      for(int i = 1; i <= Q; i++) {

            int l, r, x;
            cin >> l >> r >> x; 

            st.update(1, 1, N - 1, l - 1, x);
            st.update(1, 1, N - 1, r, -x);

            cout << st.t[1].dp[1][1] << '\n';
      }

}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 5 ms 4700 KB Output is correct
9 Correct 3 ms 4700 KB Output is correct
10 Correct 3 ms 4700 KB Output is correct
11 Correct 3 ms 4700 KB Output is correct
12 Correct 3 ms 4568 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 5 ms 4700 KB Output is correct
9 Correct 3 ms 4700 KB Output is correct
10 Correct 3 ms 4700 KB Output is correct
11 Correct 3 ms 4700 KB Output is correct
12 Correct 3 ms 4568 KB Output is correct
13 Correct 275 ms 35668 KB Output is correct
14 Correct 283 ms 38036 KB Output is correct
15 Correct 271 ms 37940 KB Output is correct
16 Correct 303 ms 37980 KB Output is correct
17 Correct 262 ms 37752 KB Output is correct
18 Correct 268 ms 38372 KB Output is correct