Submission #849792

#	Time	Username	Problem	Language	Result	Execution time	Memory
849792		gun_gan	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	5 ms	39516 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 2e5 + 5;

int N, Q;
int A[MX];

struct segtree {

      struct node {
            ll leftMax = 0, leftMin = 0, rightMax = 0, rightMin = 0, x = 0;
            bool alone = 0;
      };

      node t[4 * MX];
      ll lazy[4 * MX];

      void push(int v, int l, int r) {
            if(lazy[v] == 0) return;

            t[v].leftMax += lazy[v];
            t[v].leftMin += lazy[v];
            t[v].rightMax += lazy[v];
            t[v].rightMin += lazy[v];

            if(l != r) {
                  lazy[v * 2 + 0] += lazy[v];
                  lazy[v * 2 + 1] += lazy[v];
            }

            lazy[v] = 0;
      }

      node merge(int a, int b) {
            // if not intersecting

            node res;

            if(t[a].rightMax < t[b].leftMin) {
                  res.x += t[a].x;
                  res.x += t[b].x;
                  res.x += t[b].leftMin - t[a].rightMax;
                  res.alone = t[a].alone && t[b].alone;
            }

            if(t[a].rightMin > t[b].leftMax) {
                  res.x += t[a].x;
                  res.x += t[b].x;
                  res.x += t[a].rightMin - t[b].leftMax;
                  res.alone = t[a].alone && t[b].alone;
            }

            if(t[a].rightMax < t[b].leftMin || t[a].rightMin > t[b].leftMax) {

                  if(t[a].alone && t[b].alone) {
                        res.leftMin = min(t[a].leftMin, t[b].leftMin);
                        res.rightMin = res.leftMin;
                        res.leftMax = max(t[a].leftMax, t[b].leftMax);
                        res.rightMax = res.leftMax;

                  } else if(t[a].alone) {
                        res.leftMin = min(t[a].leftMin, t[b].leftMin);
                        res.leftMax = max(t[a].leftMax, t[b].leftMax);

                        res.rightMin = t[b].rightMin;
                        res.rightMax = t[b].rightMax;

                  } else if(t[b].alone) {
                        res.leftMin = t[a].leftMin;
                        res.leftMax = t[a].leftMax;

                        res.rightMin = min(t[a].rightMin, t[b].rightMin);
                        res.rightMax = max(t[a].rightMax, t[b].rightMax);

                  } else {
                        res.leftMin = t[a].leftMin;
                        res.leftMax = t[a].leftMax;
                        res.rightMin = t[b].rightMin;
                        res.rightMax = t[b].rightMax;
                  }

                  return res;
            }
            // somehow intersecting

            res.x += t[a].x;
            res.x += t[b].x;
            res.leftMin = t[a].leftMin;
            res.leftMax = t[a].leftMax;
            res.rightMin = t[b].rightMin;
            res.rightMax = t[b].rightMax;

            return res;
      } 

      void update(int v, int l, int r, int ql, int qr, int x) {
            push(v, l, r);
            if(l > qr || r < ql) return;
            if(ql <= l && qr >= r) {
                  lazy[v] += x;
                  push(v, l, r);
                  return;
            }
            int mid = (l + r) >> 1;
            update(v * 2 + 0, l, mid + 0, ql, qr, x);
            update(v * 2 + 1, mid + 1, r, ql, qr, x);
            t[v] = merge(v * 2 + 0, v * 2 + 1);
      }

      void build(int v, int l, int r) {
            if(l == r) {
                  t[v].x = 0;
                  t[v].alone = 1;
                  t[v].leftMin = t[v].leftMax = t[v].rightMin = t[v].rightMax = A[l];
                  return;
            }
            int mid = (l + r) >> 1;
            build(v * 2 + 0, l, mid + 0);
            build(v * 2 + 1, mid + 1, r);
            t[v] = merge(v * 2 + 0, 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];

      st.build(1, 1, N);

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

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

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

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

}

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