[CSES] Projects

const ll N = 4e5 + 4;
ll tr[4 * N], a[N];
ll pull(ll l, ll r)
{
    ll p = max(l, r); // operation
    return p;
}
void build(ll node, ll l, ll r)
{
    if (l == r)
        tr[node] = a[l];
    else
    {
        ll mid = l + (r - l) / 2;
        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);

        tr[node] = pull(tr[node * 2], tr[node * 2 + 1]);
    }
}
void update(ll node, ll l, ll r, ll index, ll val)
{
    if (index > r || index < l)
        return;
    if (l == r)
        a[index] = val, tr[node] = val; // update operation
    else
    {
        ll mid = l + (r - l) / 2;
        update(node * 2, l, mid, index, val);
        update(node * 2 + 1, mid + 1, r, index, val);

        tr[node] = pull(tr[node * 2], tr[node * 2 + 1]);
    }
}
ll query(ll node, ll l, ll r, ll start, ll end)
{
    if (end < l || start > r)
        return -inf; // operation (inf , -inf , 0 ...)
    else if (start <= l && end >= r)
        return tr[node];
    else
    {
        ll mid = l + (r - l) / 2;
        ll p1 = query(2 * node, l, mid, start, end);
        ll p2 = query(2 * node + 1, mid + 1, r, start, end);

        return pull(p1, p2); // operation
    }
}
// build(1,0,n-1) .... query(1,0,n-1,l,r) .... update(1,0,n-1,x,a[x])

void solve()
{
    ll n;
    cin >> n;

    vpll l, r;
    vll p;

    map<ll, ll> mp;
    rep(i, n)
    {
        ll x, y, z;
        cin >> x >> y >> z;
        l.pb({x, i});
        r.pb({y, i});
        p.pb(z);
        mp[x]++;
        mp[y]++;
    }

    vll dp(n + 1, 0LL);

    ll cnt = 0LL;
    for (auto &x : mp)
        x.s = cnt++;

    sort(all(l));
    build(1, 0, cnt);

    debug(mp);
    debug(l);

    FOR(i, 0, n - 1)
    {
        ll index = l[i].s;
        ll x = l[i].f, y = r[index].f, z = p[index];

        dp[i] = p[index];
        if (i)
        {
            ll mx = query(1, 0, cnt, 0, mp[x] - 1);
            if (mx < inf)
                dp[i] = max(dp[i], z + mx);
        }
        update(1, 0, cnt, mp[y], max(a[mp[y]], dp[i]));
    }

    debug(dp);

    ll ans = 0LL;
    rep(i, n) ans = max(ans, dp[i]);

    cout << ans << "\n";
}