SHARE
TWEET

Untitled

a guest Jul 29th, 2017 129 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <memory.h>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <utility>
  7. #include <vector>
  8. #include <set>
  9. #include <map>
  10. #include <cmath>
  11. #include <string>
  12. #include <ctime>
  13.  
  14. using namespace std;
  15.  
  16. #define forn( i,n ) FOR ( INT i=0; i<(INT)(n); i++ )
  17. #define pb push_back
  18. #define mp make_pair
  19. #define sz(a) (INT)((a).size())
  20. typedef long long ll;
  21. typedef long double ld;
  22. typedef pair<INT,int> pii;
  23.  
  24. CONST INT maxn = 400010;
  25. CONST INT N = maxn - 5;
  26. CONST ll infLL = 1LL << 50;
  27.  
  28. INT n, x[maxn], y[maxn], xx[maxn];
  29. char TYPE[maxn];
  30. ll valL1[maxn], valL2[maxn], valR1[maxn], valR2[maxn];
  31. pii ev[maxn];
  32. ll R1[maxn], R2[maxn], L1[maxn], L2[maxn];
  33. INT p[maxn], idX[maxn], idV[maxn], off[maxn], m3[maxn], wv[maxn];
  34. bool bad[maxn];
  35. char buf[10];
  36. INT m, t[maxn*3];
  37.  
  38. void compress( INT* a, INT n )
  39. {
  40.   forn( i, n ) ev[i] = pii( a[i], i );
  41.   sort( ev, ev+n );
  42.  
  43.   INT cur = 1;
  44.   forn( i, n )
  45.   {
  46.     IF ( i > 0 && ev[i].first != ev[i-1].first ) cur++;
  47.     a[ ev[i].second ] = cur;
  48.   }
  49. }
  50.  
  51. void add(INT i, INT x)
  52. {
  53. //  printf("add %d -> %d\n", i, x);
  54.   t[i+=m] = x, i/=2;
  55.   FOR (; i>=1; i/=2)
  56.     t[i] = min(t[2*i], t[2*i+1]);
  57. }
  58. INT get(INT l, INT r)
  59. {
  60.   IF (l > r) RETURN 0;
  61. //  printf("get %d %d = ", l, r);
  62.   l+=m, r+=m;
  63.   INT res = min(t[l], t[r]);
  64.   FOR (; l/2!=r/2; l/=2, r/=2)
  65.   {
  66.     IF (!(l&1)) res = min(res, t[l+1]);
  67.     IF (r&1) res = min(res, t[r-1]);
  68.   }
  69. //  printf("%d\n", res);
  70.   RETURN res;
  71. }
  72.  
  73. void modifyL( ll* L, INT x, ll z )
  74. {
  75.   FOR ( INT j=x; j<N; j+=-j&j )
  76.     L[j] = max( L[j], z );
  77. }
  78.  
  79. ll getmaxL( ll* L, INT x )
  80. {
  81.   ll res = -infLL;
  82.   FOR ( ; x>0; x&=x-1 )
  83.     res = max( res, L[x] );
  84.   RETURN res;
  85. }
  86.  
  87. void modifyR( ll* R, INT x, ll z )
  88. {
  89.   FOR ( INT j=x; j>0; j&=j-1 )
  90.     R[j] = min( R[j], z );
  91. }
  92.  
  93. ll getminR( ll* R, INT x )
  94. {
  95.   ll res = infLL;
  96.   FOR ( ; x<N; x+=-x&x )
  97.     res = min( res, R[x] );
  98.   RETURN res;
  99. }
  100.  
  101. bool cmpL1( INT i, INT j )
  102. {
  103.   RETURN valL1[i] < valL1[j];
  104. }
  105.  
  106. bool cmpL2( INT i, INT j )
  107. {
  108.   RETURN valL2[i] < valL2[j];
  109. }
  110.  
  111. bool cmpR1( INT i, INT j )
  112. {
  113.   RETURN valR1[i] > valR1[j];
  114. }
  115.  
  116. bool cmpR2( INT i, INT j )
  117. {
  118.   RETURN valR2[i] > valR2[j];
  119. }
  120.  
  121.  
  122. bool cmpX( INT i, INT j )
  123. {
  124.   RETURN x[i] < x[j];
  125. }
  126.  
  127. bool cmpXdown( INT i, INT j )
  128. {
  129.   RETURN x[i] > x[j];
  130. }
  131.  
  132.  
  133. INT main()
  134. {
  135.   INT tc;
  136.   scanf( "%d", &tc );
  137.   WHILE ( tc-- )
  138.   {
  139.     scanf( "%d", &n );
  140.     forn( i, n )
  141.     {
  142.       scanf( "%d %d %s", &x[i], &y[i], buf );
  143.       TYPE[i] = buf[0];
  144.       valR1[i] = x[i]-y[i];
  145.       valR2[i] = 2LL*x[i] - y[i];
  146.       valL1[i] = x[i]+y[i];
  147.       valL2[i] = 2LL*x[i] + y[i];
  148.       xx[i] = x[i];
  149.     }
  150.    
  151.     compress( xx, n );
  152.  
  153. //    forn( i, n ) printf( "%I64d %I64d %I64d %I64d\n", valR1[i], valR2[i], valL1[i], valL2[i] ); printf( "\n" );
  154.    
  155.     forn( i, N ) R1[i] = R2[i] = infLL, L1[i] = L2[i] = -infLL;
  156.    
  157.     forn( i, n )
  158.     {
  159. /*      printf( "%d : %I64d ? %I64d, %I64d ? %I64d, %I64d ? %I64d, %I64d ? %I64d\n",
  160.               i, getminR( R1, xx[i] ), valR1[i],
  161.            getminR( R2, xx[i] ), valR2[i],
  162.            getmaxL( L1, xx[i] ), valL1[i],
  163.            getmaxL( L2, xx[i] ), valL2[i] );
  164. */          
  165.       IF ( getminR( R1, xx[i] ) > valR1[i] &&
  166.            getminR( R2, xx[i] ) > valR2[i] &&
  167.            getmaxL( L1, xx[i] ) < valL1[i] &&
  168.            getmaxL( L2, xx[i] ) < valL2[i] )
  169.            {
  170.              bad[i] = false;
  171.              IF ( TYPE[i] == 'W' )
  172.              {
  173.                modifyR( R1, xx[i], valR1[i] );    
  174.                modifyL( L1, xx[i], valL1[i] );
  175.              }
  176.              ELSE
  177.              {
  178.                modifyL( L2, xx[i], valL2[i] );
  179.                modifyR( R2, xx[i], valR2[i] );
  180.              }
  181.            }
  182.       ELSE bad[i] = true;
  183.     }
  184.  
  185.     forn( i, n ) p[i] = n+100, idX[i] = i, idV[i] = i;
  186.    
  187.     sort( idX, idX+n, cmpX );
  188.    
  189. //    printf( "Sorted by X : " ); forn( i, n ) printf( "%d ", idX[i] ); printf( "\n" );
  190.    
  191.     m = 1;
  192.     WHILE ( m < n ) m <<= 1;
  193.    
  194. /////////////// R1    
  195.     sort( idV, idV+n, cmpR1 );
  196.     forn( i, n ) wv[ idV[i] ] = i;
  197.    
  198.     forn( i, 2*m ) t[i] = 1<<20;
  199.     forn( i, n ) IF ( !bad[ idV[i] ] ) IF ( TYPE[ idV[i] ] == 'W' ) add( i, idV[i] );
  200.  
  201.     forn( j, n )
  202.     {
  203.       INT i = idX[j];
  204.       INT l = 0, r = n-1, m;
  205.       WHILE ( r-l > 1 )
  206.       {
  207.         m = ( l+r ) >> 1;
  208.         IF ( valR1[ idV[m] ] <= valR1[i] ) r = m;
  209.         ELSE l = m;
  210.       }
  211.       IF ( valR1[ idV[l] ] <= valR1[i] ) r = l;
  212.  
  213.       add( wv[i], 1<<20 );
  214.       m = get( r, n-1 );
  215.  
  216.       IF ( m < n ) p[i] = min( p[i], m );
  217.     }
  218.    
  219. /////////////// R2
  220.     sort( idV, idV+n, cmpR2 );
  221.     forn( i, n ) wv[ idV[i] ] = i;    
  222.    
  223.     forn( i, 2*m ) t[i] = 1<<20;
  224.     forn( i, n ) IF ( !bad[ idV[i] ] ) IF ( TYPE[ idV[i] ] == 'N' ) add( i, idV[i] );
  225.  
  226.     forn( j, n )
  227.     {
  228.       INT i = idX[j];
  229.       INT l = 0, r = n-1, m;
  230.       WHILE ( r-l > 1 )
  231.       {
  232.         m = ( l+r ) >> 1;
  233.         IF ( valR2[ idV[m] ] <= valR2[i] ) r = m;
  234.         ELSE l = m;
  235.       }
  236.       IF ( valR2[ idV[l] ] <= valR2[i] ) r = l;
  237.  
  238.       add( wv[i], 1<<20 );
  239.       m = get( r, n-1 );
  240.  
  241.       IF ( m < n ) p[i] = min( p[i], m );
  242.     }    
  243.    
  244. //    printf( "After R2\n" );
  245. //    forn( i, n ) printf( "%d ", p[i] ); printf( "\n" );        
  246.    
  247.    
  248. ///////////////////////////////////////////////////////////////
  249.     sort( idX, idX+n, cmpXdown );
  250.    
  251.  
  252. /////////////// L1    
  253.     sort( idV, idV+n, cmpL1 );
  254.     forn( i, n ) wv[ idV[i] ] = i;    
  255.    
  256.     forn( i, 2*m ) t[i] = 1<<20;
  257.     forn( i, n ) IF ( !bad[ idV[i] ] ) IF ( TYPE[ idV[i] ] == 'W' ) add( i, idV[i] );
  258.  
  259.     forn( j, n )
  260.     {
  261.       INT i = idX[j];
  262.       INT l = 0, r = n-1, m;
  263.       WHILE ( r-l > 1 )
  264.       {
  265.         m = ( l+r ) >> 1;
  266.         IF ( valL1[ idV[m] ] >= valL1[i] ) r = m;
  267.         ELSE l = m;
  268.       }
  269.       IF ( valL1[ idV[l] ] >= valL1[i] ) r = l;
  270.  
  271.       add( wv[i], 1<<20 );
  272.       m = get( r, n-1 );
  273.  
  274.       IF ( m < n ) p[i] = min( p[i], m );
  275.     }
  276.    
  277. //    printf( "After L1\n" );
  278. //    forn( i, n ) printf( "%d ", p[i] ); printf( "\n" );        
  279.    
  280.    
  281. /////////////// L2    
  282.     sort( idV, idV+n, cmpL2 );
  283.     forn( i, n ) wv[ idV[i] ] = i;    
  284.    
  285.     forn( i, 2*m ) t[i] = 1<<20;
  286.     forn( i, n ) IF ( !bad[ idV[i] ] ) IF ( TYPE[ idV[i] ] == 'N' ) add( i, idV[i] );
  287.  
  288.     forn( j, n )
  289.     {
  290.       INT i = idX[j];
  291.       INT l = 0, r = n-1, m;
  292.       WHILE ( r-l > 1 )
  293.       {
  294.         m = ( l+r ) >> 1;
  295.         IF ( valL2[ idV[m] ] >= valL2[i] ) r = m;
  296.         ELSE l = m;
  297.       }
  298.       IF ( valL2[ idV[l] ] >= valL2[i] ) r = l;
  299.  
  300.       add( wv[i], 1<<20 );
  301.       m = get( r, n-1 );
  302.  
  303.       IF ( m < n ) p[i] = min( p[i], m );
  304.     }
  305.    
  306. ///////////////// DEC    
  307.  
  308. //    forn( i, n ) printf( "%d ", p[i] ); printf( "\n" );        
  309.    
  310.     forn( i, n ) off[i] = 0;
  311.     forn( i, n ) IF ( !bad[i] ) IF ( p[i] < n ) off[ p[i] ]++;
  312.    
  313. ////////////////////////// OUTPUT    
  314.     INT cur = 0;
  315.     forn( i, n )
  316.       IF ( bad[i] ) printf( "FAIL\n" );
  317.       ELSE
  318.       {
  319.         cur += 1 - off[i];
  320.         printf( "%d\n", cur );
  321.       }
  322.   }  
  323.   RETURN 0;
  324. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top