Solução escrita por Sofhia de Souza
O problema trata-se de um line sweep. É recomendado que deem uma estudada nessa técnica, ela é útil na resolução de vários problemas.
Iremos representar cada convidado como uma struct $$pt$$, que terá os seguintes atributos: $$x$$, representando a quantidade de inteligência, $$y$$, representando o quão engraçado o convidado é, e $$d$$, o preço do presente que esse convidado irá levar.
Primeiro, será necessário que façamos uma compressão de coordenadas nas váriaveis $$x$$ e $$y$$ do vetor de structs, pois iremos trabalhar com uma BIT de frequência, e o vetor da BIT não pode ter tamanho $$10^9$$ (pois excede o limite de memória).
Após isso, com o vetor de structs ordenado pela variável $$x$$, montaremos uma matriz $$mat[][]$$, onde guardaremos no vetor $$mat[i]$$ todas as structs que possuem valor $$x$$ igual, sendo esse $$x$$ o $$i$$-ésimo menor $$x$$ diferente que aparece no vetor de structs.
Feito isso, para cada vetor $$mat[i]$$, percorreremos o mesmo e faremos uma query na nossa BIT para cada $$mat[i][j]$$, que retorna $$k$$ = quantos convidados existem na BIT com valor $$y$$ menor que o $$y$$ de $$mat[i][j]$$. Caso $$k$$ seja maior que a variável $$maior$$, inicialmente igualada a 0, igualamos o $$maior$$ a $$k$$. Após percorrer todo o vetor $$mat[i]$$, percorreremos ele novamente, agora fazendo um update na nossa BIT do valor $$y$$ de cada $$mat[i][j]$$.
No fim, basta printarmos a váriavel $$maior$$.
Como fazemos o update de cada vetor $$mat[i]$$ só depois de te-lo percorrido e antes de percorrer os vetores $$mat[t]$$ com $$t > i$$, garantimos que as queries só irão retornar a quantidade de convidados que possuem $$x$$ e $$y$$ menores que o $$x$$ e $$y$$ de $$mat[i][j]$$.
Segue o código para melhor compreensão:
| #include <bits/stdc++.h> | |
| #define pb push_back | |
| #define MAXN 100010 | |
| using namespace std; | |
| typedef long long int ll; | |
| int n; | |
| struct pt | |
| { | |
| ll x, y, d; | |
| }vet[MAXN]; | |
| vector < pt > mat[MAXN]; | |
| inline bool cmp1(pt a, pt b) | |
| { | |
| if(a.x != b.x) return a.x < b.x; | |
| return a.y < b.y; | |
| } | |
| inline bool cmp2(pt a, pt b) | |
| { | |
| if(a.y != b.y) return a.y < b.y; | |
| return a.x < b.x; | |
| } | |
| inline void comp_coord() | |
| { | |
| sort(vet, vet+n, cmp2); | |
| map < ll, int > mapa; | |
| int cont = 1; | |
| for(int i = 0 ; i < n ; i++) | |
| { | |
| if(!mapa.count(vet[i].y)) | |
| { | |
| mapa[vet[i].y] = cont++; | |
| vet[i].y = cont – 1; | |
| } | |
| else vet[i].y = mapa[vet[i].y]; | |
| } | |
| sort(vet, vet+n, cmp1); | |
| mapa.clear(); | |
| cont = 1; | |
| for(int i = 0 ; i < n ; i++) | |
| { | |
| if(!mapa.count(vet[i].x)) | |
| { | |
| mapa[vet[i].x] = cont++; | |
| vet[i].x = cont – 1; | |
| } | |
| else vet[i].x = mapa[vet[i].x]; | |
| } | |
| } | |
| ll bit[MAXN]; | |
| inline ll query(int y) | |
| { | |
| ll resp = 0; | |
| for(int i = y ; i >= 1 ; i -= i&-i) resp = max(resp, bit[i]); | |
| return resp; | |
| } | |
| inline void update(int y, ll val) | |
| { | |
| for(int i = y+1 ; i <= MAXN ; i += i&-i) bit[i] = max(bit[i], val); | |
| } | |
| int main() | |
| { | |
| cin >> n; | |
| for(int i = 0 ; i < n ; i++) | |
| { | |
| cin >> vet[i].x >> vet[i].y >> vet[i].d; | |
| } | |
| comp_coord(); | |
| int cont = -1; | |
| for(int i = 0 ; i < n ; i++) | |
| { | |
| if(i == 0 or vet[i].x != vet[i-1].x) | |
| { | |
| cont++; | |
| mat[cont].pb(vet[i]); | |
| } | |
| if(i != 0 and vet[i].x == vet[i-1].x) | |
| { | |
| if(vet[i].y != vet[i-1].y) mat[cont].pb(vet[i]); | |
| else mat[cont][mat[cont].size()-1].d += vet[i].d; //junto os que sao iguais | |
| } | |
| } | |
| ll maior = 0; | |
| for(int i = 0 ; i <= cont ; i++) | |
| { | |
| ll aux[MAXN]; | |
| for(int j = 0 ; j < mat[i].size() ; j++) | |
| { | |
| pt v = mat[i][j]; | |
| ll k = query(v.y) + v.d; | |
| aux[j] = k; | |
| maior = max(maior, k); | |
| } | |
| for(int j = 0 ; j < mat[i].size() ; j++) | |
| { | |
| update(mat[i][j].y, aux[j]); | |
| } | |
| } | |
| cout << maior << endl; | |
| } |
