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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |