CSES – Projects

#include<bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 5e5+5;
int n,L[maxn],R[maxn],profit[maxn],dp[maxn],bit[maxn];
set<int> st;
map<int,int> mp;
//
int lowbit(int x){
    return x & (-x);
}
void modify(int pos,int x){
    for(int i=pos; i<maxn; i += lowbit(i)){
        bit[i] = max(bit[i], x);
    }
}
int query(int pos){
    int ret = 0;
    for(int i=pos; i>0; i -= lowbit(i)){
        ret = max(ret, bit[i]);
    }
    return ret;
}
void disc(){
    for(int i=1;i<=n;i++) st.insert(L[i]), st.insert(R[i]);
    int cnt = 1;
    for(int i:st) mp[i] = cnt++;
    for(int i=1;i<=n;i++) L[i] = mp[L[i]], R[i] = mp[R[i]];
}
signed main(){
    fastio;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>L[i]>>R[i]>>profit[i];
    disc();
    vector<int> ord(n); iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [](int i,int j){
        return L[i] < L[j];
    });
    for(int i:ord){
        int x = query(L[i]-1) + profit[i];
        dp[R[i]] = x;
        modify(R[i], x);
    }
    cout<<*max_element(dp+1,dp+maxn)<<"\n";
    return 0;
}