Submission #1113965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113965		sunboi	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	6 ms	20816 KiB

Main

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

const int N = 2e5 + 1000;
vector<int> a(N);
vector<pair<int, int>> t(4 * N);
vector<int> lazy(4 * N);

void push(int v, int vl, int vr){
    if (lazy[v]){
            t[2 * v].first += lazy[v];
            t[2 * v].second+= lazy[v];
            
            t[2 * v + 1].first += lazy[v];
            t[2 * v + 1].second+= lazy[v];
            
            lazy[2 * v] += lazy[v];
            lazy[2 * v + 1] += lazy[v];
            lazy[v] = 0;   
    }
}

void build(int v, int vl, int vr) {
    if (vl == vr) {
        t[v] = {a[vl], a[vl]};
        return;
    }
    int vm = (vl + vr) / 2;
    
    build(2 * v, vl, vm);
    build(2 * v + 1, vm + 1, vr);
    
    t[v] = {max(t[2 * v].first, t[2 * v + 1].first), min(t[2 * v].second, t[2 * v + 1].second)};
}

void update(int v, int vl, int vr, int l, int r, int x){
    if (vl > r || vr < l) return;
    if (vl >= l && vr <= r){
        t[v].first += x;
        t[v].second += x;
        lazy[v] += x;
        return;
    }
    push(v, vl ,vr);
    int vm = (vl + vr) / 2;
    
    update(2 * v, vl, vm, l, r, x);
    update(2 * v + 1, vm + 1, vr, l, r, x);

    t[v] = {max(t[2 * v].first, t[2 * v + 1].first), min(t[2 * v].second, t[2 * v + 1].second)};
}

int get(int v, int vl, int vr, int l, int r){
    if (vl > r || vr < l) return 0;

    push(v, vl, vr);
     
    int node = t[v].first - t[v].second;
    int izq = t[2 * v].first - t[2 * v].second;
    int der = t[2 * v + 1].first - t[2 * v + 1].second;
    
    if (vr - vl == 1 || node > izq + der){
        return node;
    }else{
         int vm = (vl + vr) / 2;
        if (vl < vm) izq = get(2 * v, vl, vm, l, r);
        if (vm + 1 < vr) der = get(2 * v + 1, vm + 1, vr, l, r);
        return izq + der;
    }
   
   
    
}

signed main()
{
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    build(1, 0, n - 1);
    while(m--){
        int l, r, x;
        cin >> l >> r >> x;
        l--; r--;
        update(1,0 , n - 1, l, r, x);
        cout << get(1,0 , n - 1, 0, n - 1) << endl;
    }
}

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