Untitled
#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; set<int> st; map<int, int> m; for (int i = 1; i <= n; i++) { cin >> a[i].l >> a[i].r >> a[i].p; st.insert(a[i].l); st.insert(a[i].r); } int i = 1; for (auto a : st) m[a] = i++; for (int i = 1; i <= n; i++) a[i].l = m[a[i].l], a[i].r = m[a[i].r]; 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, a[i].l - 1); dp[i] = max(dp[i], mx + a[i].p); } t.upd(1, 1, n, a[i].r, dp[i]); } int mx = 0; for (int i = 1; i <= n; i++) mx = max(mx, dp[i]); cout << mx << '\n'; }
Leave a Comment