Solução por Sofhia Souza
Para resolver este problema, é necessário conhecimento sobre BIT e struct.
Para que um aluno seja excelente, não pode existir nenhum cara que tenham os 3 valores menores que ele (lembrando que quanto menor o valor da colocação, maior a nota do aluno). Então, verificaremos para cada cara se existe algum aluno que tenha os 3 valores menores que o dele. Faremos isso da seguinte forma:
Guardamos em uma struct as 3 colocações e o indice do aluno. Chamemos as colocações de $$a$$,$$b$$, e $$c$$. Ordenamos o vetor pelas colocações $$a$$. Em seguida, percorremos o vetor e usamos uma BIT para guardarmos o menor valor de $$c$$ que existe em alunos que possuem colocações $$b$$ menores que o meu $$b$$, e caso a menor nota $$c$$ seja maior que o meu $$c$$, significa que eu sou excelente. Segue abaixo o código para melhor entendimento:
| #include <bits/stdc++.h> | |
| #define MAXN 100010 | |
| #define inf 1000000 | |
| using namespace std; | |
| int n, bit[MAXN]; | |
| struct cmpt | |
| { | |
| int a, b, c; | |
| bool operator <(cmpt &k) const | |
| { | |
| return a < k.a; | |
| } | |
| }vet[MAXN]; | |
| int query(int x) | |
| { | |
| int resp = inf; | |
| for(int i = x ; i > 0 ; i -= i & (-i)) | |
| resp = min(resp, bit[i]); //pego o menor valor de c de todos que tem o b menor que eu | |
| return resp; | |
| } | |
| void update(int x, int val) | |
| { | |
| for(int i = x ; i < MAXN ; i += i & (-i)) | |
| bit[i] = min(bit[i], val); | |
| } | |
| int main() | |
| { | |
| int t; | |
| cin >> t; | |
| while(t–) //rodo a quantidade de casos de teste | |
| { | |
| memset(bit, inf, sizeof bit); //igualo toda a bit ao meu valor máximo | |
| cin >> n; | |
| for(int i = 0 ; i < n ; i++) | |
| { | |
| cin >> vet[i].a >> vet[i].b >> vet[i].c; | |
| } | |
| sort(vet, vet+n); //ordeno pelo menor a | |
| int cont = 0; // variavel que conta a quantidade de alunos excelentes | |
| for(int i = 0 ; i < n ; i++) | |
| { | |
| int b = vet[i].b, c = vet[i].c; | |
| int k = query(b); //chamo minha query | |
| if(k > c) cont++; //se esse valor for maior que meu c, significa que não existe nenhum cara melhor que eu, logo eu sou excelente | |
| update(b, c); //adiciono o valor de c na minha bit | |
| } | |
| cout << cont << endl; | |
| } | |
| } |

Comente