Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pf printf
- #define sc scanf
- #define endl "\n"
- #define dbug(x) cout << #x << ": " << x << endl
- #define gi(k) scanf("%d",&k)
- #define gl(k) scanf("%lld",&k)
- #define pb push_back
- #define nl puts ("")
- #define sp printf ( " " )
- #define phl printf ( "hello\n" )
- #define ff first
- #define ss second
- #define POPCOUNT __builtin_popcountll
- #define RIGHTMOST __builtin_ctzll
- #define LEFTMOST(x) (63-__builtin_clzll((x)))
- #define MP make_pair
- #define rep(i,n) for(int i = 1; i <= n; i++)
- #define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
- #define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
- #define CLR(x,y) memset(x,y,sizeof(x))
- #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
- #define MIN(a,b) ((a)<(b)?(a):(b))
- #define MAX(a,b) ((a)>(b)?(a):(b))
- #define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
- #define SQ(x) ((x)*(x))
- #define ABS(x) ((x)<0?-(x):(x))
- #define FABS(x) ((x)+eps<0?-(x):(x))
- #define ALL(x) (x).begin(),(x).end()
- #define LCM(x,y) (((x)/gcd((x),(y)))*(y))
- #define SZ(x) ((vlong)(x).size())
- #define NORM(x) if(x>=mod) x-=mod;if(x<0) x+=mod;
- #define MOD(x,y) (((x)*(y))%mod)
- #define ODD(x) (((x)&1)==0?(0):(1))
- #define Set(N,cur) N=(N|(1LL<<cur))
- #define Reset(N,cur) N=(N&(~(1LL<<cur)))
- #define Check(N,cur) (!((N&(1LL<<cur))==0))
- #define fast_cin ios_base::sync_with_stdio(false);cin.tie(NULL)
- #define NMAX 2147483647
- #define LMAX 9223372036854775807LL
- #define mem CLR
- using namespace std;
- #define LL long long
- #define LLU long long unsigned int
- typedef long long vlong;
- typedef unsigned long long uvlong;
- typedef pair < int, int > pii;
- typedef pair < vlong, vlong > pll;
- typedef vector<int> vi;
- typedef vector<vlong> vl;
- typedef vector<pll> vll;
- inline vlong gcd ( vlong a, vlong b ) {
- a = ABS ( a ); b = ABS ( b );
- while ( b ) { a = a % b; swap ( a, b ); } return a;
- }
- const vlong inf = 2147383647;
- const vlong mod = 1000000007;
- const double pi = 2 * acos ( 0.0 );
- const double eps = 1e-9;
- int t,n,tr[100005],ar[100005],br[100005],cr[100005],val[100005],pos[100005];
- int query(int idx) {
- int res = NMAX;
- while(idx > 0) {
- res = min(res,tr[idx]);
- idx -= idx & (-idx);
- }
- return res;
- }
- void update(int idx, int num) {
- while(idx <= n) {
- tr[idx] = min(tr[idx],num);
- idx += idx & (-idx);
- }
- }
- int main () {
- #ifdef forthright48
- freopen ( "00_input.txt", "r", stdin ); //freopen ( "00_output.txt", "w", stdout );
- #endif
- gi(t);
- rep(kas,t) {
- gi(n);
- int ans = 0, id;
- rep(i,n) {
- gi(ar[i]); gi(br[i]); gi(cr[i]);
- }
- rep(i,n) {
- val[ar[i]] = i;
- }
- rep(i,n) {
- br[i] = val[br[i]];
- cr[i] = val[cr[i]];
- pos[cr[i]] = i;
- }
- mem(tr,63);
- rep(i,n) {
- id = pos[br[i]];
- if(query(id) > br[i]) ans++;
- update(id,br[i]);
- }
- cout << ans << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement