Solução Informática Avançado - Semana 63

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: