Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
2.2 kB
3
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) (x).begin(), (x).end()
#define f(i, n) for (int i = 0; i < n; i++)
#define trace(x) cerr << #x << ": " << x << '\n'
const int N = 2e5 + 9;

struct seg
{
    int l, r, p;
} a[N];
struct ST
{
    int t[4 * N];
    static const int inf = 1e9;
    ST()
    {
        memset(t, 0, sizeof t);
    }
    void build(int n, int b, int e)
    {
        if (b == e)
        {
            t[n] = 0;
            return;
        }
        int mid = (b + e) >> 1, l = n << 1, r = l | 1;
        build(l, b, mid);
        build(r, mid + 1, e);
        t[n] = max(t[l], t[r]);
    }
    void upd(int n, int b, int e, int i, int x)
    {
        if (b > i || e < i)
            return;
        if (b == e && b == i)
        {
            t[n] = max(t[n], x);
            return;
        }
        int mid = (b + e) >> 1, l = n << 1, r = l | 1;
        upd(l, b, mid, i, x);
        upd(r, mid + 1, e, i, x);
        t[n] = max(t[l], t[r]);
    }
    int query(int n, int b, int e, int i, int j)
    {
        if (b > j || e < i)
            return -inf;
        if (b >= i && e <= j)
            return t[n];
        int mid = (b + e) >> 1, l = n << 1, r = l | 1;
        int L = query(l, b, mid, i, j);
        int R = query(r, mid + 1, e, i, j);
        return max(L, R);
    }
} t;

bool cmp(seg a, seg b)
{
    return a.r < b.r;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].l >> a[i].r >> a[i].p;
    }
    sort(a + 1, a + n + 1, cmp);
    vector<int> dp(N, 0);
    // t.build(1, 1, N);
    for (int i = 1; i <= n; i++)
    {
        dp[i] = a[i].p;
        // for (int j = 1; j < i; j++)
        // {
        //     if (a[j].r < a[i].l)
        //     {
        //         dp[i] = max(dp[i], dp[j] + a[i].p);
        //     }
        // }
        if (i > 1)
        {
            int mx = t.query(1, 1, N, 1, i - 1);
            dp[i] = max(dp[i], mx + a[i].p);
        }
        t.upd(1, 1, N, i, dp[i]);
    }
    int mx = 0;
    for (int i = 1; i <= n; i++)
        mx = max(mx, dp[i]);
    cout << mx << '\n';
}
Leave a Comment