Submission #1061509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061509		PanosPask	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	1 ms	344 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e18;

struct SegTree {
    struct Node {
        // segments[0]: The minimum and maximum of the leftmost segment in the Nod
        // segments[1]: The minimum and maximum of the rightmost segment in the Node
        ll segments[2][2] = {{0, 0}, {0, 0}};

        // Is the whole segment unitied
        bool unite = true;
        bool is_def = false;

        ll ans = 0;

        ll calc_segment(int i) {
            return segments[i][1] - segments[i][0];
        }

        Node(void) {
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    segments[i][j] = 0;
                }
            }

            ans = 0;
            unite = true;
            is_def = false;
        }
    };

    void update(Node& a, int x) {
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                a.segments[i][j] += x;
            }
        }
    }

    Node solo(int v) {
        Node res;
        
        update(res, v);

        return res;
    }

    Node merge(Node& a, Node& b) {
        Node res;

        if (b.is_def) {
            res = a;
            res.unite = false;

            return res;
        }

        ll ans = a.ans + b.ans;
        res.segments[0][0] = a.segments[0][0];
        res.segments[0][1] = a.segments[0][1];
        res.segments[1][0] = b.segments[1][0];
        res.segments[1][1] = b.segments[1][1];
        if (max(a.segments[1][0], b.segments[0][0]) > min(a.segments[1][1], b.segments[1][1])) {
            // Merge the 2 things

            ll mx = max(a.segments[1][1], b.segments[0][1]);
            ll mn = min(a.segments[1][0], b.segments[0][0]);

            ans += mx - mn - a.calc_segment(1) - b.calc_segment(0);

            if (a.unite) {
                res.segments[0][0] = mn;
                res.segments[0][1] = mx;
            }
            if (b.unite) {
                res.segments[1][0] = mn;
                res.segments[1][1] = mx;
            }
            if (a.unite && b.unite) {
                res.unite;
            }

        }
        res.ans = ans;

        return res;
    }

    Node DEFAULT;
    const int NO_OP = 0;
    int size;
    vector<Node> tree;
    vector<int> op;

    void init(int N) {
        size = 1; 
        while (size < N) {
            size *= 2;
        }

        DEFAULT.is_def = true;

        tree.assign(2 * size, DEFAULT);
        op.assign(2 * size, NO_OP);
    }

    void propagate(int x) {
        update(tree[2 * x + 1], op[x]);
        update(tree[2 * x + 2], op[x]);
        op[2 * x + 1] += op[x];
        op[2 * x + 2] += op[x];

        op[x] = NO_OP;
    }

    void add(int l, int r, int v, int x, int lx, int rx) {
        if (lx >= r || l >= rx) {
            return;
        }
        else if (l <= lx && rx <= r) {
            update(tree[x], v);
            tree[x].is_def = false;
            op[x] += v;

            return;
        }

        propagate(x);

        int mid = (lx + rx) / 2;
        add(l, r, v, 2 * x + 1, lx, mid);
        add(l, r, v, 2 * x + 2, mid, rx);

        tree[x] = merge(tree[2 * x + 1], tree[2 * x + 2]);
    }
    void add(int l, int r, int v) {
        add(l, r, v, 0, 0, size);
    }

    Node calc(int l, int r, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return DEFAULT;
        }
        else if (l <= lx && rx <= r) {
            return tree[x];
        }

        int mid = (lx + rx) / 2;

        Node n1 = calc(l, r, 2 * x + 1, lx, mid);
        Node n2 = calc(l, r, 2 * x + 2, mid, rx);

        return merge(n1, n2);
    }
    ll calc(int l, int r) {
        return calc(l, r, 0, 0, size).ans;
    }
};

int N, Q;
SegTree st;

int main(void)
{
    scanf("%d %d", &N, &Q);

    st.init(N);

    for (int i = 0; i < N; i++) {
        int v;
        scanf("%d", &v);
        st.add(i, i + 1, v);
    }

    while (Q--) {
        int l, r, x;
        scanf("%d %d %d", &l, &r, &x);
        l--;

        st.add(l, r, x);

        printf("%lld\n", st.calc(0, N));
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'SegTree::Node SegTree::merge(SegTree::Node&, SegTree::Node&)':
Main.cpp:86:21: warning: statement has no effect [-Wunused-value]
   86 |                 res.unite;
      |                 ~~~~^~~~~
Main.cpp: In function 'int main()':
Main.cpp:171:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |     scanf("%d %d", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:177:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |         scanf("%d", &v);
      |         ~~~~~^~~~~~~~~~
Main.cpp:183:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |         scanf("%d %d %d", &l, &r, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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