// 入力制約チェック #pragma GCC optimize ( "O3" ) #pragma GCC optimize( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #include #include #include #include #include #include using namespace std; using ll = long long; #define MAIN main #define TYPE_OF( VAR ) remove_const::type >::type #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE #define CIN( LL , A ) LL A; cin >> A #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES ) #define QUIT return 0 #define COUT( ANSWER ) cout << ( ANSWER ) << "\n"; #define RETURN( ANSWER ) COUT( ANSWER ); QUIT class Query { public: list m_ST[2]; ll m_M; }; void Merge( list& S_to , list& S_from ) { auto itr = S_to.begin() , end = S_to.end(); while( ! S_from.empty() ){ const int& t = S_from.front(); bool not_inserted = true; while( itr != end && not_inserted ){ if( t < *itr ){ S_to.insert( itr , t ); not_inserted = false; } else { itr++; } } if( not_inserted ){ S_to.push_back( t ); } S_from.pop_front(); } return; } int MAIN() { UNTIE; CEXPR( int , bound_NQ , 1e3 ); CIN_ASSERT( N , 1 , bound_NQ ); CIN_ASSERT( Q , 1 , bound_NQ ); list query{}; CEXPR( ll , bound_M , 1e9 ); int temp; REPEAT( Q ){ CIN_ASSERT( A , 0 , N ); CIN_ASSERT( B , 0 , N ); CIN_ASSERT( M , -bound_M , bound_M ); temp = 1; query.push_back( Query() ); Query& query_curr = query.back(); list& m_S = query_curr.m_ST[0]; CIN( string , S ); assert( S == "S" ); REPEAT( A ){ CIN_ASSERT( Si , temp , N ); temp = Si + 1; m_S.push_back( Si ); } temp = 1; list& m_T = query_curr.m_ST[1]; CIN( string , T ); assert( T == "T" ); REPEAT( B ){ CIN_ASSERT( Ti , temp , N ); temp = Ti + 1; m_T.push_back( Ti ); } query_curr.m_M = M; } while( ! query.empty() ){ auto itr = query.begin() , end = query.end(); list::iterator itr0 , itr1; temp = 0; int count = 0 , i0 , i1; while( itr != end ){ while( ( ! itr->m_ST[0].empty() && ! itr->m_ST[1].empty() ) ? itr->m_ST[0].back() == itr->m_ST[1].back() : false ){ itr->m_ST[0].pop_back(); itr->m_ST[1].pop_back(); } bool empty = true; FOR( i , 0 , 2 ){ list& m_STi = itr->m_ST[i]; if( ! m_STi.empty() ){ if( empty ){ empty = false; } int& m_STi_back = m_STi.back(); if( temp < m_STi_back ){ temp = m_STi_back; count = 1; itr0 = itr; i0 = i; } else if( temp == m_STi_back ){ count = 2; itr1 = itr; i1 = i; } } } if( empty ){ if( 0 > itr->m_M ){ itr = query.erase( itr ); } else { RETURN( "Yes" ); } } else { itr++; } } if( count == 1 ){ query.erase( itr0 ); } else if( count == 2 ){ if( i0 == i1 ){ query.erase( itr0 ); query.erase( itr1 ); } else { list& m_S0 = itr0->m_ST[0]; list& m_T0 = itr0->m_ST[1]; list& m_S1 = itr1->m_ST[0]; list& m_T1 = itr1->m_ST[1]; if( i0 == 0 ){ m_S0.pop_back(); } else { m_T0.pop_back(); } if( i1 == 0 ){ m_S1.pop_back(); } else { m_T1.pop_back(); } if( m_S0.size() + m_T0.size() < m_S1.size() + m_T1.size() ){ Merge( m_S1 , m_S0 ); Merge( m_T1 , m_T0 ); itr1->m_M += itr0->m_M; query.erase( itr0 ); } else { Merge( m_S0 , m_S1 ); Merge( m_T0 , m_T1 ); itr0->m_M += itr1->m_M; query.erase( itr1 ); } } } } RETURN( "No" ); }