Final Array

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N (1<<19)
 
ll t[2*N];
 
void push(int s, int l, int r){
    if(l+1 == r || t[s] == 0) return;
    
    t[2*s] = max(t[2*s], t[s]);
    t[2*s+1] = max(t[2*s+1], t[s] + (ll)(r-l)/2);
    t[s] = 0;
}
 
void upd(int s, int l, int r, int a, int b, ll x){
    if(a==l && b==r) t[s] = max(t[s], x);
    else{
        push(s, l, r);
        int m = (l+r)/2;
        if(a < m) upd(2*s, l, m, a, min(b, m), x);
        if(b > m) upd(2*s+1, m, r, max(a, m), b, x + (ll)max(0, m-a));
    }
}
 
void asd(int s, int l, int r){
    if(l + 1 == r) return;
    push(s, l, r);
    int m = (l+r)/2;
    asd(2*s, l, m);
    asd(2*s+1, m, r);
}
int main() {
    int n, m;
    cin >> n >> m;
    while(m--){
        int a, b;
        ll x; cin >> a >> b >> x;
        upd(1, 0, N, a, b+1, x);        
    }
    asd(1, 0, N);
    for(int i=1; i<=n; ++i) cout << t[N+i] << " ";
    cout << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED