noic-intermediario-s71.cpp

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

const int maxn = 1e5+10;

struct node
{
	ll b, f, d;

	bool operator<(const node& o) const 
	{
		if(b != o.b) return b < o.b; // ordeno pela menor beleza 
		else return f > o.f; // em caso de empate, pela maior fortuna
	}
} c[maxn];

int n, m;
ll bit[2*maxn]; // declaro a BIT com o dobro da quantidade de posições para o caso de todos os valores de fortuna e beleza serem diferentes
vector<node> candidatos;

void repeat() // junto os candidatos com a mesma fortuna e a mesma beleza
{
	ll dd = 0LL;

	for(int i = 1 ; i <= n ; ++i)
	{
		if(c[i].b == c[i - 1].b && c[i].f == c[i - 1].f) // se o candidado i e i-1 possuem a mesma beleza e fortuna
        	{
		    dd += c[i].d; // somo as doações deles
		}
		else
		{
			if(i > 1) candidatos.push_back({c[i - 1].b, c[i - 1].f, dd}); // adiciono o candidato no vector
			dd = c[i].d; // atualizo a doação do i-ésimo candidato
		}
	}

	candidatos.push_back({c[n].b, c[n].f, dd}); // adiono o n-ésimo cadidato
}

void compress() // comprimo os valores de beleza e fortuna
{
	map<ll, ll> M;

	for(int i = 1 ; i <= n ; ++i) M[c[i].b] = M[c[i].f] = 0LL;

	int amf = 0;

	for(auto it = M.begin() ; it != M.end() ; ++it)
	{
		it->second = ++amf;
	}

	for(int i = 1 ; i <= n ; ++i)
	{
		c[i].b = M[c[i].b];
		c[i].f = M[c[i].f];
	}
	
	m = amf;

	sort(c + 1, c + n + 1); // ordeno os candidatos

	repeat(); // junto os caras com a mesma beleza e fortuna
}

void update(int p, ll val) // update na BIT
{
	for(int i = p; i <= m && i; i += (i & -i))
	{
		bit[i] = max(bit[i], val);
	}
}

ll query(int p) // query na BIT
{
	ll ans = 0LL;

	for(int i = p ; i > 0 ; i -= (i & -i))
	{
		ans = max(bit[i], ans);
	}

	return ans;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> n;

	for(int i = 1 ; i <= n ; ++i)
	{
		ll b, f, d;
		cin >> b >> f >> d;

		c[i] = {b, f, d};
	}

	compress(); // comprimo os valores de beleza e fortuna

	ll ans = 0LL;

	for(auto u: candidatos) // processo os candidatos
	{
		ll at = query(u.f - 1); // consulto a melhor resposta para o u candidato

		at += u.d; // adiono a doação dele

		ans = max(at, ans); // atualizo a resposta

		update(u.f, at); // adiciono na BIT a resposta para u-ésimo cadidato
	}

	cout << ans << '\n'; // imprimo a resposta
}