SSEQ (VOI 2022)

#define task "SSEQ"
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
using ll = long long;

template<class T>
void read(T &x) {
    x = 0;
    register int c;

    while((c = getchar()) && (c > '9' || c < '0'));

    for(; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

template<class T>
void readneg(T &x) {
    x = 0;
    register int c;
    bool neg = 0;

    while((c = getchar()) && (c > '9' || c < '0'))
        if(c == '-')
            neg = 1;

    for(; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';

    if(neg) x = -x;
}

constexpr int N = 1e6 + 5;
int n;
struct Segment{
    int l, r;
    ll w;
} a[N];

vector<int> s, in[N];

void Read() {
    //cin >> n;
    read(n);

    for(int i = 1; i <= n; ++i)
        //cin >> a[i].l >> a[i].r >> a[i].w;
        read(a[i].l), read(a[i].r), readneg(a[i].w);
}

void Sub_1() {
    for(int i = 1; i <= n; ++i) {
        s.emplace_back(a[i].l);
        s.emplace_back(a[i].r);
    }

    sort(s.begin(), s.end());
    s.resize(unique(s.begin(), s.end()) - s.begin());

    ll ans(0);

    for(int i = 0; i < (int)s.size(); ++i)
        for(int j = i; j < (int)s.size(); ++j) {
            ll res(0);

            for(int t = 1; t <= n; ++t)
                if(s[i] <= a[t].l && a[t].r <= s[j])
                    res += a[t].w;

            ans = max(ans, res);
        }

    cout << ans;
}

struct SegmentTree {
    int n;
    ll st[N * 4], lazy[N * 4];

    SegmentTree() {
        n = 1e6;
        memset(lazy, 0, sizeof lazy);
        memset(st, 0, sizeof st);
    }

    void Push(int id) {
        if(lazy[id]) {
            st[id << 1] += lazy[id];
            lazy[id << 1] += lazy[id];
            st[id << 1 | 1] += lazy[id];
            lazy[id << 1 | 1] += lazy[id];
            lazy[id] = 0;
        }
    }

    void Update(int id, int l, int r, const int &a, const int &b, const ll &v) {
        if(l > b || r < a) return;
        if(l >= a && r <= b) {
            st[id] += v;
            lazy[id] += v;
            return;
        }

        Push(id);

        Update(id << 1, l, (l + r) / 2, a, b, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, a, b, v);

        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }

    void Update(int l, int r, ll v) {
        Update(1, 1, n, l, r, v);
    }

    ll Get(int id, int l, int r, const int &a, const int &b) {
        if(l > b || r < a) return 0;

        if(l >= a && r <= b) return st[id];

        Push(id);

        return max(Get(id << 1, l, (l + r) / 2, a, b), Get(id << 1 | 1, (l + r) / 2 + 1, r, a, b));
    }

    ll Get(int l, int r) {
        return Get(1, 1, n, l, r);
    }
} f;

void Sub_4() {
    for(int i = 1; i <= n; ++i)
        in[a[i].r].emplace_back(i);

    ll ans(0);


    for(int i = 1; i <= 1e6; ++i) {
        for(auto j : in[i])
            f.Update(1, a[j].l, a[j].w);
        ans = max(ans, f.Get(1, i));
    }

    cout << ans;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(task".INP", "r")) {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    Read();

    if(n <= 200)
        Sub_1();
    else
        Sub_4();
}