Created
May 14, 2019 15:26
-
-
Save sofhiasouza/a1beb7e97f41093172ef20b4128f27f9 to your computer and use it in GitHub Desktop.
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment