Submission #932240

#	Time	Username	Problem	Language	Result	Execution time	Memory
932240		tkm_algorithms	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	1 ms	348 KiB

Main

#include<bits/stdc++.h>

#define ll long long

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int inf = 1e9;

struct seg {

    struct node {
        int mx, mn;
    };

    vector<node> tree;
    int size;

    void init(int n) {
        size = 1;
        while (size < n)size *= 2;
        tree.assign(2 * size, {0, 0});
    }

    node combine(node a, node b) {
        if (a.mx - b.mn > b.mx - a.mn)return {a.mx, b.mn};
        else return {b.mx, a.mn};
    }

    void set(int i, int v, int ex, int x, int lx, int rx) {
        if (rx - lx == 1) {
            tree[x] = {v + ex, v + ex};
            return;
        }
        int mid = (lx + rx) >> 1;
        if (i < mid)set(i, v, ex, 2 * x + 1, lx, mid);
        else set(i, v, ex, 2 * x + 2, mid, rx);
        tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
    }

    void set(int i, int v, int ex) {
        set(i, v, ex, 0, 0, size);
    }

    node ans(int l, int r, int x, int lx, int rx) {
        if (lx >= r || l >= rx)return {-inf, inf};
        if (lx >= l && rx <= r)return tree[x];
        int mid = (lx + rx) >> 1;
        auto p = combine(ans(l, r, 2 * x + 1, lx, mid), ans(l, r, 2 * x + 2, mid, rx));
        return p;
    }

    node ans(int l, int r) {
        ans(l, r, 0, 0, size);
    }
};

int32_t main() {
    fast
    int n, q;
    cin >> n >> q;
    seg st;
    st.init(n);
    vector<int> a;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        a.push_back(x);
        st.set(i, x, 0);
    }
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        --l;
        for (int i = l; i < r; ++i) {
            st.set(i, a[i], x);
            a[i] += x;
        }
        cout << st.tree[0].mx - st.tree[0].mn << endl;
    }
    return 0;
}
/*
 * @Nargulyev
 */

Compilation message (stderr)

Main.cpp: In member function 'seg::node seg::ans(int, int)':
Main.cpp:56:5: warning: no return statement in function returning non-void [-Wreturn-type]
   56 |     }
      |     ^

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