Submission #1291253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291253		datluong_04	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	401 ms	37876 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define FOR(i , a , b) for(int i = a ; i <= b;  i++)
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define maxn 200005

ll a[maxn] , d[maxn];

int sgn(ll x){
    if(x < 0) return -1;
    if(x > 0) return 1;
    return 0;
}

struct Node{
    ll dp[2][2];
    int signL , signR;
    Node(){
        dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = -1e18;
        signL = signR = 0;
    }
};

struct Segtree{
    int n;
    vector<Node> seg;
    Segtree(int _n = 0){ init(_n);}
    void init(int _n){
        n = _n;
        if(n > 0) seg.assign(4 * n + 5 , Node());
        else seg.clear();
    }

    Node combine(Node a , Node b){
        Node c;
        if(a.signL != 0 || a.signR != 0) c.signL = a.signL;
        else c.signL = b.signL;
        if(b.signL != 0 || b.signR != 0) c.signR = b.signR;
        else c.signR = a.signR;

        // [  ] [  ]
        // l  m o  r

        FOR(l , 0 , 1){
            FOR(r , 0 , 1){
                ll best = -1e18;
                FOR(m , 0 , 1){
                    FOR(o , 0 , 1){
                        ll va = a.dp[l][m];
                        ll vb = b.dp[o][r];
                        if(va == -1e18 || vb == -1e18) continue;
                        if(m && o) if(a.signR * b.signL < 0) continue;
                        best = max(best , va + vb);
                    }
                }
                c.dp[l][r] = best;
            }
        }
        return c;
    }

    void build(int id , int l , int r){
        if(l == r){
            Node nd;
            ll val = d[l];
            nd.signL = nd.signR = sgn(val);
            nd.dp[0][0] = 0;
            nd.dp[0][1] = nd.dp[1][0] = -1e18;
            nd.dp[1][1] = llabs(val);
            seg[id] = nd;
            return;
        }

        int mid = (l + r) / 2;
        build(2 * id , l , mid);
        build(2 * id + 1, mid + 1 , r);
        seg[id] = combine(seg[2 * id] , seg[2 * id + 1]);
    }

    void update(int id , int l , int r , int pos ,ll val){
        if(pos < l || pos > r) return;
        if(l == r){
            Node nd;
            ll val = d[l];
            nd.signL = nd.signR = sgn(val);
            nd.dp[0][0] = 0;
            nd.dp[0][1] = nd.dp[1][0] = -1e18;
            nd.dp[1][1] = llabs(val);
            seg[id] = nd;
            return;
        }

        int mid = (l + r) / 2;
        if(pos <= mid) update(2 * id , l , mid , pos , val);
        else update(2 * id + 1, mid + 1 , r , pos , val);
        seg[id] = combine(seg[2 * id] , seg[2 * id + 1]);
    }

    ll query(){
        ll ans = -1e18;
        FOR(l , 0 , 1) FOR(r , 0 , 1) ans = max(ans ,seg[1].dp[l][r]);
        if(ans == -1e18) return 0;
        return ans;
    }
};


int main(){
    FAST;
    int n , q;
    cin >> n >> q;
    FOR(i , 1 , n) cin >> a[i];
    if(n == 1){
        FOR(_ , 1 , q){
            int l , r;
            ll x;
            cin >> l >> r >> x;
            cout <<  0 << "\n";
        }
        return 0;
    }

    FOR(i , 1 , n - 1) d[i] = a[i + 1] - a[i];
    Segtree st(n - 1);
    st.build(1 , 1 , n - 1);

    FOR(_ , 1 , q){
        int l , r;
        ll x;
        cin >> l >> r >> x;
        if(l > 1){
            d[l - 1] += x;
            st.update(1 , 1 , n - 1, l - 1 , d[l - 1]);
        }
        if(r < n){
            d[r] -= x;
            st.update(1 , 1 , n - 1, r , d[r]);
        }
        cout << st.query() << "\n";
    }
}

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