Submission #641509

#	Time	Username	Problem	Language	Result	Execution time	Memory
641509		leroycut	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	724 ms	58572 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

struct node{
    ll val[2][2] = {};
    ll lval = 0, rval = 0;
    node() {}
    node(ll x){
        lval = rval = x;
        val[0][0] = 0;
        val[1][0] = 0;
        val[0][1] = 0;
        val[1][1] = abs(x);
    }

    void upd(ll v){
        lval += v;
        rval += v;
        val[1][1] = abs(lval);
    }
};


struct segtree{
    node op(node &l, node &r){
        node res;
        res.lval = l.lval;
        res.rval = r.rval;
        for(int ll = 0; ll < 2; ++ll){
            for(int lr = 0; lr < 2; ++lr){
                for(int rl = 0; rl < 2; ++rl){
                    for(int rr = 0; rr < 2; ++rr){
                        if(lr && rl){
                            if((l.rval <= 0 && r.lval <= 0) || (l.rval >= 0 && r.lval >= 0)){
                                res.val[ll][rr] = max(res.val[ll][rr], l.val[ll][lr] + r.val[rl][rr]);    
                            }
                        }else{
                            res.val[ll][rr] = max(res.val[ll][rr], l.val[ll][lr] + r.val[rl][rr]);
                        }
                    }
                }
            }
        }
        return res;
    }

    node cur;
    int L, R, m;
    segtree *left, *right;
    
    segtree(int l, int r, vector<node> &num){
        L = l;
        R = r;
        m = (l + r) / 2;
        if(r - l == 1){
            cur = num[l];
            return;
        }
        left = new segtree(l, m, num), right = new segtree(m, r, num);
        cur = op(left->cur, right->cur);
    }

    void update(int i, ll v){
        if(R - L == 1){
            cur.upd(v);
            return;
        }
        if(i < m){
            left->update(i, v);
        }else{
            right->update(i, v);
        }
        cur = op(left->cur, right->cur);
    }
};



int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;
    vector<ll> v(n);
    vector<node> a(n - 1);
    for(int i = 0; i < n; ++i) cin >> v[i];
    for(int i = 0; i < n - 1; ++i) a[i] = node(v[i + 1] - v[i]);

    segtree sg(0, n - 1, a);

    while(q--){
        int l, r;
        ll x;
        cin >> l >> r >> x;
        l--;
        if(l - 1 >= 0){
            sg.update(l - 1, x);
        }
        if(r < n){
            sg.update(r - 1, -x);
        }
        cout << sg.cur.val[1][1] << "\n";
    }
}

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