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 
,
, e 
. Ordenamos o vetor pelas colocações . Em seguida, percorremos o vetor e usamos uma BIT para guardarmos o menor valor de que existe em alunos que possuem colocações menores que o meu , e caso a menor nota seja maior que o meu , significa que eu sou excelente. Segue abaixo o código para melhor entendimento:
This file contains 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 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; | |
| } | |
| } |