Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <memory.h>
- #include <cstdlib>
- #include <algorithm>
- #include <iostream>
- #include <utility>
- #include <vector>
- #include <set>
- #include <map>
- #include <cmath>
- #include <string>
- #include <ctime>
- using namespace std;
- #define forn( i,n ) for ( int i=0; i<(int)(n); i++ )
- #define pb push_back
- #define mp make_pair
- #define sz(a) (int)((a).size())
- typedef long long ll;
- typedef long double ld;
- typedef pair<int,int> pii;
- const int maxn = 200010;
- const int N = maxn - 5;
- const ll infLL = 1LL << 50;
- int n, x[maxn], y[maxn], xx[maxn];
- char type[maxn];
- ll valL1[maxn], valL2[maxn], valR1[maxn], valR2[maxn];
- pii ev[maxn];
- ll R1[maxn], R2[maxn], L1[maxn], L2[maxn];
- bool bad[maxn];
- char buf[10];
- void compress( int* a, int n )
- {
- forn( i, n ) ev[i] = pii( a[i], i );
- sort( ev, ev+n );
- int cur = 1;
- forn( i, n )
- {
- if ( i > 0 && ev[i].first != ev[i-1].first ) cur++;
- a[ ev[i].second ] = cur;
- }
- }
- void modifyL( ll* L, int x, ll z )
- {
- for ( int j=x; j<N; j+=-j&j )
- L[j] = max( L[j], z );
- }
- ll getmaxL( ll* L, int x )
- {
- ll res = -infLL;
- for ( ; x>0; x&=x-1 )
- res = max( res, L[x] );
- return res;
- }
- void modifyR( ll* R, int x, ll z )
- {
- for ( int j=x; j>0; j&=j-1 )
- R[j] = min( R[j], z );
- }
- ll getminR( ll* R, int x )
- {
- ll res = infLL;
- for ( ; x<N; x+=-x&x )
- res = min( res, R[x] );
- return res;
- }
- int main()
- {
- int tc;
- scanf( "%d", &tc );
- while ( tc-- )
- {
- scanf( "%d", &n );
- forn( i, n )
- {
- scanf( "%d %d %s", &x[i], &y[i], buf );
- type[i] = buf[0];
- valR1[i] = x[i]-y[i];
- valR2[i] = 2LL*x[i] - y[i];
- valL1[i] = x[i]+y[i];
- valL2[i] = 2LL*x[i] + y[i];
- xx[i] = x[i];
- }
- compress( xx, n );
- // forn( i, n ) printf( "%I64d %I64d %I64d %I64d\n", valR1[i], valR2[i], valL1[i], valL2[i] ); printf( "\n" );
- forn( i, N ) R1[i] = R2[i] = infLL, L1[i] = L2[i] = -infLL;
- forn( i, n )
- {
- /* printf( "%d : %I64d ? %I64d, %I64d ? %I64d, %I64d ? %I64d, %I64d ? %I64d\n",
- i, getminR( R1, xx[i] ), valR1[i],
- getminR( R2, xx[i] ), valR2[i],
- getmaxL( L1, xx[i] ), valL1[i],
- getmaxL( L2, xx[i] ), valL2[i] );
- */
- if ( getminR( R1, xx[i] ) > valR1[i] &&
- getminR( R2, xx[i] ) > valR2[i] &&
- getmaxL( L1, xx[i] ) < valL1[i] &&
- getmaxL( L2, xx[i] ) < valL2[i] )
- {
- bad[i] = false;
- if ( type[i] == 'W' )
- {
- modifyR( R1, xx[i], valR1[i] );
- modifyL( L1, xx[i], valL1[i] );
- }
- else
- {
- modifyL( L2, xx[i], valL2[i] );
- modifyR( R2, xx[i], valR2[i] );
- }
- }
- else bad[i] = true;
- }
- forn( i, n ) p[i] = -1, id[i] = i, idV[i] = i;
- sort( id, id+n, Xincr );
- sort( idV, idV+n, cmpR1 );
- forn( i, N ) R1[i] = infLL;
- // forn( i, n ) modifyR( R1, i, valR1[
- forn( j, n )
- {
- int i = id[j];
- }
- forn( i, n ) printf( "%d ", bad[i] );
- printf( "\n" );
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement