Language: C++

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 2 * 1e5;

typedef long long ll;

mt19937 randomGen(2708199);

struct it
{
    int l, r;
    ll c;

    bool operator<(it other) const
    {
        return l < other.l || (l == other.l && r < other.r);
    }
};

struct Treap
{
    Treap *left, *right;
    int priority;
    int keyL, keyR, c;
    int value;
    ll value2;

    Treap(int _keyL, int _keyR, ll _c)
    {
        keyL = _keyL; keyR = _keyR;
        c = _c;
        value = keyL;
        value2 = c;
        priority = randomGen();
        left = nullptr; right = nullptr;
    }

    void recalc()
    {
        value = keyL;
        value2 = c;

        if(left != nullptr)
        {
            value2 += left->value2;
            value = min(value, left->value);
        }
        if(right != nullptr)
        {
            value2 += right->value2;
            value = min(value, right->value);
        }
    }
};

Treap* merge(Treap* sm, Treap* bg)
{
    if(sm == nullptr)
    {
        return bg;
    }
    if(bg == nullptr)
    {
        return sm;
    }

    if(sm->priority > bg->priority)
    {
        sm->right = merge(sm->right, bg);
        sm->recalc();
        return sm;
    }
    else
    {
        bg->left = merge(sm, bg->left);
        bg->recalc();
        return bg;
    }
}

pair <Treap*, Treap*> split(Treap* t, int key)
{
    if(t == nullptr)
    {
        return {nullptr, nullptr};
    }
    if(t->keyR < key)
    {
        auto splitResults = split(t->right, key);
        t->right = splitResults.first;
        t->recalc();
        return {t, splitResults.second};
    }
    else
    {
        auto splitResults = split(t->left, key);
        t->left = splitResults.second;
        t->recalc();
        return {splitResults.first, t};
    }
}

Treap* root = nullptr;

void lkr(Treap* t)
{
    if(t == nullptr) return;
    lkr(t->left);
    printf("%d %d\n", t->keyL, t->keyR);
    lkr(t->right);
}

void add(int keyL, int keyR, ll c)
{
    if(root == nullptr)
    {
        root = new Treap(keyL, keyR, c);
    }
    else
    {
        Treap* t = new Treap(keyL, keyR, c);
        //printf("%d\n", t->value);

        auto splitResults = split(root, keyR);
        root = merge(merge(splitResults.first, t), splitResults.second);
    }
}

pair <int, ll> query(int keyR)
{
    auto splitResults = split(root, keyR);
    int answer = -1;
    ll sum = 0;
    if(splitResults.second != nullptr)
    {
        answer = splitResults.second->value;
        sum = splitResults.second->value2;
    }
    root = merge(splitResults.first, splitResults.second);
    return {answer, sum};
}

int n, m;
it a[MAXN];
ll T[MAXN];
int sumss[MAXN];

void read_input()
{
    scanf("%d %d", &n, &m);

    for(int i = 0; i < m; i++)
    {
        scanf("%d %d %lld", &a[i].l, &a[i].r, &a[i].c);
    }
    sort(a, a + m);
}

ll get_query(int index)
{
    if(index < 0) return 0;
    return T[index];
}

void solve()
{
    int j = 0;
    ll prev = 0;
    for(int i = 0; i <= n; i++)
    {
        sumss[i] = sumss[i - 1];
        while(j < m && a[j].l <= i)
        {
            //printf("%d %d\n", a[j].l, a[j].r);
            sumss[i] += a[j].c;
            add(a[j].l, a[j].r, a[j].c);
            j++;
        }
        auto answers = query(i);
        int mostL = answers.first;
        ll sum = answers.second;
        //lkr(root);
        //printf("%d %d %d\n", i, mostL, sum);
        //activ[i] = sum;
        T[i] = max(prev, sum + get_query(mostL - 1));
        //T[i] = max(T[i], sum + get_query(mostL) - (sumss[i] - sumss[mostL - 1]));
        prev = max(prev, T[i]);
    }
    printf("%lld\n", prev);
}

int main()
{
    read_input();
    solve();

    return 0;
}

/*
6 9
5 5 3
0 1 10
1 6 -8
3 6 5
3 4 9
5 5 -2
1 3 -6
4 6 -7
1 2 5
*/


Compiler output:
a.cc:10:1: error: 'mt19937' does not name a type
   10 | mt19937 randomGen(2708199);
      | ^~~~~~~
a.cc: In constructor 'Treap::Treap(int, int, ll)':
a.cc:37:20: error: 'randomGen' was not declared in this scope; did you mean 'random_r'?
   37 |         priority = randomGen();
      |                    ^~~~~~~~~
      |                    random_r