Submission #1246593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246593		Leo121	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	0 ms	320 KiB

Main

#include <bits/stdc++.h>

using namespace std;

// #include <tr2/dynamic_bitset>
// using custom_bitset = tr2::dynamic_bitset<>;

#define pb push_back
#define rbg(v) v.rbegin()
#define bg(v) v.begin()
#define all(v) v.begin(), v.end()
#define SZ(v) int(v.size())
#define MP make_pair
#define fi first
#define se second
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define for0(i, n) forn(i, 0, n - 1)
#define for1(i, n) forn(i, 1, n)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define far0(i, n) fora(i, n - 1, 0)
#define far1(i, n) fora(i, n, 1)
#define foru(i, v) for(auto & i : v)
#define fors(i, a, b, c) for(int i = a; i <= b; i += c)
#define lb lower_bound
#define ub upper_bound
#define ord1(s, n) s + 1, s + int(n) + 1
#define ord0(s, n) s, s + int(n)
#define debug(x) cout << #x << " = " << x << endl
#define debugsl(a) cout << #a << " = " << a << ", "



//#include <bits/extc++.h>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, bool> ib;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vii> vvii;
typedef vector<vb> vvb;
typedef vector<char> vc;
typedef long double ld;
typedef double db;
//typedef __int128 Int;

const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
//const ll inf = 1e18;

const int MX = 4e5;

struct ure {
    ll sum;
    ll lmn, lmx;
    ll rmn, rmx;
    bool all;
    ll lazy;
};

vector<ure> st;

ure merge(ure l, ure r) {
    if(l.rmx < r.lmn || l.rmn > r.lmx)
        return {
            l.sum + r.sum + ((l.rmx < r.lmn) ? r.lmn - l.rmx : l.rmn - r.lmx),
            (l.all) ? min(l.lmn, r.lmn) : l.lmn, (l.all) ? max(l.lmx, r.lmx) : l.lmx,
            (r.all) ? min(l.rmn, r.rmn) : r.rmn, (r.all) ? max(l.rmx, r.rmx) : r.rmx,
            (l.all && r.all), 0
        };
    return {
        l.sum + r.sum,
        l.lmn, l.lmx,
        r.rmn, r.rmx,
        0, 0
    };
}

void build(int node, int l, int r, vi & arr) {
    if(l == r) {
        st[node] = {0, arr[l], arr[l], arr[l], arr[l], 1, 0};
        return;
    }
    int m = (l + r) >> 1;
    build((node << 1) | 1, l, m, arr);
    build((node << 1) + 2, m + 1, r, arr);
    st[node] = merge(st[(node << 1) | 1], st[(node << 1) + 2]);
}

void push(int node, int l, int r) {
    if(!st[node].lazy) return;
    if(l < r) {
        st[(node << 1) | 1].lazy += st[node].lazy;
        st[(node << 1) + 2].lazy += st[node].lazy;
    }   
    st[node].lmn += st[node].lazy;
    st[node].rmn += st[node].lazy;
    st[node].lmx += st[node].lazy;
    st[node].rmx += st[node].lazy;
    st[node].lazy = 0;
}

void update(int node, int l, int r, int a, int b, int v) {
    push(node, l, r);
    if(l > b || r < a) return;
    if(a <= l && r <= b) {
        st[node].lazy += v;
        push(node, l, r);
        return;
    }
    int m = (l + r) >> 1;
    update((node << 1) | 1, l, m, a, b, v);
    update((node << 1) + 2, m + 1, r, a, b, v);
    st[node] = merge(st[(node << 1) | 1], st[(node << 1) + 2]);
}

void solve () {
    int n, q;
    cin >> n >> q;
    st = vector<ure>(4 * n);
    vi arr(n);
    for0(i, n) cin >> arr[i];
    build(0, 0, n - 1, arr);
    while(q --) {
        int l, r, x;
        cin >> l >> r >> x;
        update(0, 0, n - 1, l - 1, r - 1, x);
        cout << st[0].sum << '\n';
    }
}

int main () 
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // freopen("palpath.out", "w", stdout);
    // freopen("palpath.in", "r", stdin);
    int t = 1;
    // cin >> t;
    for1(i, t){
        //cout << "Case " << i << ": ";
        solve();
        cout << '\n';
    }
    return 0;
}

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