Submission #850181

#	Time	Username	Problem	Language	Result	Execution time	Memory
850181		gun_gan	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	303 ms	38372 KiB

Main

#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 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55