Advertisement
Guest User

Untitled

a guest
Jan 17th, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.97 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define pf printf
  4. #define sc scanf
  5. #define endl "\n"
  6. #define dbug(x) cout << #x << ": " << x << endl
  7. #define gi(k) scanf("%d",&k)
  8. #define gl(k) scanf("%lld",&k)
  9. #define pb push_back
  10. #define nl puts ("")
  11. #define sp printf ( " " )
  12. #define phl printf ( "hello\n" )
  13. #define ff first
  14. #define ss second
  15. #define POPCOUNT __builtin_popcountll
  16. #define RIGHTMOST __builtin_ctzll
  17. #define LEFTMOST(x) (63-__builtin_clzll((x)))
  18. #define MP make_pair
  19. #define rep(i,n) for(int i = 1; i <= n; i++)
  20. #define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
  21. #define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
  22. #define CLR(x,y) memset(x,y,sizeof(x))
  23. #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
  24. #define MIN(a,b) ((a)<(b)?(a):(b))
  25. #define MAX(a,b) ((a)>(b)?(a):(b))
  26. #define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
  27. #define SQ(x) ((x)*(x))
  28. #define ABS(x) ((x)<0?-(x):(x))
  29. #define FABS(x) ((x)+eps<0?-(x):(x))
  30. #define ALL(x) (x).begin(),(x).end()
  31. #define LCM(x,y) (((x)/gcd((x),(y)))*(y))
  32. #define SZ(x) ((vlong)(x).size())
  33. #define NORM(x) if(x>=mod) x-=mod;if(x<0) x+=mod;
  34. #define MOD(x,y) (((x)*(y))%mod)
  35. #define ODD(x) (((x)&1)==0?(0):(1))
  36. #define Set(N,cur) N=(N|(1LL<<cur))
  37. #define Reset(N,cur) N=(N&(~(1LL<<cur)))
  38. #define Check(N,cur) (!((N&(1LL<<cur))==0))
  39. #define fast_cin ios_base::sync_with_stdio(false);cin.tie(NULL)
  40. #define NMAX 2147483647
  41. #define LMAX 9223372036854775807LL
  42. #define mem CLR
  43.  
  44. using namespace std;
  45.  
  46.  
  47. #define LL long long
  48. #define LLU long long unsigned int
  49. typedef long long vlong;
  50. typedef unsigned long long uvlong;
  51. typedef pair < int, int > pii;
  52. typedef pair < vlong, vlong > pll;
  53. typedef vector<int> vi;
  54. typedef vector<vlong> vl;
  55. typedef vector<pll> vll;
  56.  
  57. inline vlong gcd ( vlong a, vlong b ) {
  58.     a = ABS ( a ); b = ABS ( b );
  59.     while ( b ) { a = a % b; swap ( a, b ); } return a;
  60. }
  61.  
  62.  
  63. const vlong inf = 2147383647;
  64. const vlong mod = 1000000007;
  65. const double pi = 2 * acos ( 0.0 );
  66. const double eps = 1e-9;
  67.  
  68.  
  69. int t,n,tr[100005],ar[100005],br[100005],cr[100005],val[100005],pos[100005];
  70.  
  71. int query(int idx) {
  72.     int res = NMAX;
  73.  
  74.     while(idx > 0) {
  75.         res = min(res,tr[idx]);
  76.         idx -= idx & (-idx);
  77.     }
  78.  
  79.     return res;
  80. }
  81.  
  82. void update(int idx, int num) {
  83.     while(idx <= n) {
  84.         tr[idx] = min(tr[idx],num);
  85.         idx += idx & (-idx);
  86.     }
  87. }
  88.  
  89. int main () {
  90.    
  91.     #ifdef forthright48
  92.     freopen ( "00_input.txt", "r", stdin ); //freopen ( "00_output.txt", "w", stdout );
  93.     #endif
  94.  
  95.     gi(t);
  96.  
  97.     rep(kas,t) {
  98.  
  99.         gi(n);
  100.  
  101.         int ans = 0, id;
  102.  
  103.         rep(i,n) {
  104.             gi(ar[i]); gi(br[i]); gi(cr[i]);
  105.         }
  106.        
  107.         rep(i,n) {
  108.             val[ar[i]] = i;
  109.         }
  110.  
  111.         rep(i,n) {
  112.             br[i] = val[br[i]];
  113.             cr[i] = val[cr[i]];
  114.            
  115.             pos[cr[i]] = i;
  116.         }
  117.  
  118.         mem(tr,63);
  119.  
  120.         rep(i,n) {
  121.             id = pos[br[i]];
  122.             if(query(id) > br[i]) ans++;
  123.        
  124.             update(id,br[i]);
  125.         }
  126.  
  127.         cout << ans << endl;
  128.     }
  129.  
  130.  
  131.     return 0;
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement