Final Array

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

const int N=1<<17;

ll st[2*N];

void setv(int a, int b, ll v){
    a+=N;
    b+=N;
    while (a<=b){
        if (a%2){
            st[a]=max(st[a], v);
            a++;
        }
        if (!(b%2)){
            st[b]=max(st[b], v);
            b--;
        }
        a/=2;
        b/=2;
    }
}

ll getv(int i){
    ll v=-1e9;
    for (i=(i+N);i;i/=2){
        v=max(v, st[i]);
    }
    return v;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for (int i=0;i<2*N;i++){
        st[i]=-1e9;
    }
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        setv(i, i, -i);
    }
    for (int i=0;i<m;i++){
        int a,b;
        ll x;
        cin>>a>>b>>x;
        x-=a;
        setv(a, b, x);
    }
    for (int i=1;i<=n;i++){
        ll tv=getv(i);
        tv+=i;
        cout<<tv<<" ";
    }
    cout<<endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED