Submission #405204

#	Time	Username	Problem	Language	Result	Execution time	Memory
405204		tsaraf	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	18 ms	37852 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()

// for an incr segment it always makes sense to the max and mn and same is true for a decr segment 
// 1 7 6 3
// 7 - 1 + 6 - 3 = 6 + 3

// when should we merge 2 segments 
// mx1 - mn1 + mx2 - mn2 <= max(mx1, mx2) - min(mn1, mn2)
// mx1 + mx2 - max(mx1, mx2) <= mn1 + mn2 - min(mn1, mn2)
// min(mx1, mx2) <= max(mn1, mn2)

// would this lead in a cascading effect ?
// no proved.

// so for each L, R i should know the value of the last and first segments mx and mn 

class Node{
    public:
    int cnt;
    ll preMax, sufMax, preMin, sufMin, ans;
    Node(ll val = 0){
        preMax = sufMax = preMin = sufMin = val;
        ans = 0;
        cnt = 1;
    }
    void add(ll val){
        preMax += val;
        sufMax += val;
        preMin += val;
        sufMin += val;
    }
};

const int N = 200 * 1000 + 3;

Node t[N << 2];
ll lazy[N << 2];
int a[N];
int n, Q;

void push(int rt){
    lazy[rt << 1] += lazy[rt];
    lazy[rt << 1 | 1] += lazy[rt];
    t[rt << 1].add(lazy[rt]);
    t[rt << 1 | 1].add(lazy[rt]);
    lazy[rt] = 0;
}

void merge(int rt){
    bool can = min(t[rt << 1].sufMax, t[rt << 1 | 1].preMax) < max(t[rt << 1].sufMin, t[rt << 1 | 1].preMin);
    t[rt].cnt = t[rt << 1].cnt + t[rt << 1 | 1].cnt - can;
    if(can && t[rt].cnt == 1){
        t[rt].ans = 0;
        t[rt].cnt = 1;
        t[rt].preMax = max(t[rt << 1].preMax, t[rt << 1 | 1].preMax);
        t[rt].preMin = min(t[rt << 1].preMin, t[rt << 1 | 1].preMin);
        t[rt].sufMax = t[rt].preMax;
        t[rt].sufMin = t[rt].preMin;
    } else {
        t[rt].preMax = t[rt << 1].preMax;
        t[rt].preMin = t[rt << 1].preMin;
        t[rt].sufMax = t[rt << 1 | 1].sufMax;
        t[rt].sufMin = t[rt << 1 | 1].sufMin;
        if(!can){
            t[rt].ans = t[rt << 1].ans + t[rt << 1 | 1].ans + (t[rt << 1].cnt > 1) * (t[rt << 1].sufMax - t[rt << 1].sufMin) + (t[rt << 1 | 1].cnt > 1)*(t[rt << 1 | 1].preMax - t[rt << 1 | 1].preMin);
        } else {
            if(t[rt << 1].cnt == 1){
                t[rt].preMax = max(t[rt << 1].preMax, t[rt << 1 | 1].preMax);
                t[rt].preMin = min(t[rt << 1].preMin, t[rt << 1 | 1].preMin);
            } else if(t[rt << 1 | 1].cnt == 1) {
                t[rt].sufMax = max(t[rt << 1].sufMax, t[rt << 1 | 1].sufMax);
                t[rt].sufMin = min(t[rt << 1].sufMin, t[rt << 1 | 1].sufMin);
            }
            t[rt].ans = t[rt << 1].ans + t[rt << 1 | 1].ans + (t[rt << 1].cnt > 1 && t[rt << 1 | 1].cnt > 1)*(max(t[rt << 1].sufMax, t[rt << 1 | 1].preMax) - min(t[rt << 1].sufMin, t[rt << 1 | 1].preMin));
        }
    }
}

void upd(int L, int R, int val, int rt = 1, int tl = 1, int tr = n){
    if(tl > R || tr < L){ return; }
    if(tl != tr && lazy[rt] != 0){ push(rt); }
    if(tl >= L && tr <= R){
        lazy[rt] += val;
        t[rt].add(val);
    } else {
        int mid = tl + tr >> 1;
        upd(L, R, val, rt << 1, tl, mid);
        upd(L, R, val, rt << 1 | 1, mid + 1, tr);
        merge(rt);
    }
}

void solve(){
    
    cin >> n >> Q;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        upd(i, i, a[i]);
    }
    while(Q--){
        int L, R, x; cin >> L >> R >> x;
        upd(L, R, x);
        if(t[1].cnt == 1){ cout << t[1].preMax - t[1].preMin << '\n'; }
        else{ cout << t[1].ans + t[1].preMax + t[1].sufMax - t[1].preMin - t[1].sufMin << '\n'; }
    }
    
}


int main(){
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif

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

    int t = 1;
    // cin >> t;


    for(int i = 1; i <= t; i++){
        // cout << "Case #" << i << ": ";

        solve();

    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:93:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |         int mid = tl + tr >> 1;
      |                   ~~~^~~~

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