SHARE
TWEET

Untitled

a guest Jul 29th, 2017 124 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 = 200010;
  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. bool bad[maxn];
  34. char buf[10];
  35.  
  36. void compress( int* a, int n )
  37. {
  38.   forn( i, n ) ev[i] = pii( a[i], i );
  39.   sort( ev, ev+n );
  40.  
  41.   int cur = 1;
  42.   forn( i, n )
  43.   {
  44.     if ( i > 0 && ev[i].first != ev[i-1].first ) cur++;
  45.     a[ ev[i].second ] = cur;
  46.   }
  47. }
  48.  
  49. void modifyL( ll* L, int x, ll z )
  50. {
  51.   for ( int j=x; j<N; j+=-j&j )
  52.     L[j] = max( L[j], z );
  53. }
  54.  
  55. ll getmaxL( ll* L, int x )
  56. {
  57.   ll res = -infLL;
  58.   for ( ; x>0; x&=x-1 )
  59.     res = max( res, L[x] );
  60.   return res;
  61. }
  62.  
  63. void modifyR( ll* R, int x, ll z )
  64. {
  65.   for ( int j=x; j>0; j&=j-1 )
  66.     R[j] = min( R[j], z );
  67. }
  68.  
  69. ll getminR( ll* R, int x )
  70. {
  71.   ll res = infLL;
  72.   for ( ; x<N; x+=-x&x )
  73.     res = min( res, R[x] );
  74.   return res;
  75. }
  76.  
  77. int main()
  78. {
  79.   int tc;
  80.   scanf( "%d", &tc );
  81.   while ( tc-- )
  82.   {
  83.     scanf( "%d", &n );
  84.     forn( i, n )
  85.     {
  86.       scanf( "%d %d %s", &x[i], &y[i], buf );
  87.       type[i] = buf[0];
  88.       valR1[i] = x[i]-y[i];
  89.       valR2[i] = 2LL*x[i] - y[i];
  90.       valL1[i] = x[i]+y[i];
  91.       valL2[i] = 2LL*x[i] + y[i];
  92.       xx[i] = x[i];
  93.     }
  94.    
  95.     compress( xx, n );
  96.  
  97. //    forn( i, n ) printf( "%I64d %I64d %I64d %I64d\n", valR1[i], valR2[i], valL1[i], valL2[i] ); printf( "\n" );
  98.    
  99.     forn( i, N ) R1[i] = R2[i] = infLL, L1[i] = L2[i] = -infLL;
  100.    
  101.     forn( i, n )
  102.     {
  103. /*      printf( "%d : %I64d ? %I64d, %I64d ? %I64d, %I64d ? %I64d, %I64d ? %I64d\n",
  104.               i, getminR( R1, xx[i] ), valR1[i],
  105.            getminR( R2, xx[i] ), valR2[i],
  106.            getmaxL( L1, xx[i] ), valL1[i],
  107.            getmaxL( L2, xx[i] ), valL2[i] );
  108. */          
  109.       if ( getminR( R1, xx[i] ) > valR1[i] &&
  110.            getminR( R2, xx[i] ) > valR2[i] &&
  111.            getmaxL( L1, xx[i] ) < valL1[i] &&
  112.            getmaxL( L2, xx[i] ) < valL2[i] )
  113.            {
  114.              bad[i] = false;
  115.              if ( type[i] == 'W' )
  116.              {
  117.                modifyR( R1, xx[i], valR1[i] );    
  118.                modifyL( L1, xx[i], valL1[i] );
  119.              }
  120.              else
  121.              {
  122.                modifyL( L2, xx[i], valL2[i] );
  123.                modifyR( R2, xx[i], valR2[i] );
  124.              }
  125.            }
  126.       else bad[i] = true;
  127.     }
  128.    
  129.     forn( i, n ) printf( "%d ", bad[i] );
  130.     printf( "\n" );
  131.   }  
  132.   return 0;
  133. }
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
 
Top