Advertisement
Guest User

Untitled

a guest
Oct 10th, 2015
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.06 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int bitTree[100002];
  4. struct contestRank
  5. {
  6. int c1,c2,c3;
  7. };
  8. bool cmp(const contestRank &a,const contestRank &b)
  9. {
  10. return a.c1<b.c1;
  11. }
  12. void update(int i,int value,int n)
  13. {
  14. while(i<=n){
  15. bitTree[i]=min(bitTree[i],value);
  16. i += (i & -i);
  17. }
  18. }
  19. int readTree(int i)
  20. {
  21. int preMin=INT_MAX;
  22. while(i){
  23. preMin=min(bitTree[i],preMin);
  24. i -= (i & -i);
  25. }
  26. return preMin;
  27. }
  28.  
  29.  
  30. int main()
  31. {
  32. int test;
  33. scanf("%d",&test);
  34. for(int p=1;p<=test;p++){
  35. int n;
  36. scanf("%d",&n);
  37. contestRank ranks[n];
  38. for(int i=0;i<n;i++){
  39. scanf("%d%d%d",&ranks[i].c1,&ranks[i].c2,&ranks[i].c3);
  40. }
  41. sort(ranks,ranks+n,cmp);
  42. fill(bitTree,bitTree+n+2,INT_MAX);
  43. int excellent=0;
  44. for(int i=0;i<n;i++){
  45. int curr=readTree(ranks[i].c2);
  46. if(curr>ranks[i].c3){
  47. excellent++;
  48. }
  49. update(ranks[i].c2,ranks[i].c3,n);
  50. }
  51. printf("%d\n",excellent);
  52. }
  53. return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement