#pragma GCC optimize ( "O3" ) #pragma GCC optimize( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #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 FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) #define QUIT return 0 #define COUT( ANSWER ) cout << ( ANSWER ) << "\n" // 通常の二分探索その1 // EXPRESSIONがANSWERの狭義単調増加関数の時、EXPRESSION >= TARGETを満たす最小の整数を返す。 // 広義単調増加関数を扱いたい時は等号成立の処理を消す。 #define BS1( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ ll ANSWER; \ { \ ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \ ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \ while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \ VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \ found = true; \ break; \ } else { \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \ VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \ } else { \ VARIABLE_FOR_BINARY_SEARCH_L = ANSWER + 1; \ } \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ } \ } \ } \ // 通常の二分探索その3 // EXPRESSIONがANSWERの狭義単調減少関数の時、EXPRESSION >= TARGETを満たす最大の整数を返す。 // 広義単調減少関数を扱いたい時は等号成立の処理を消す。 #define BS3( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ ll ANSWER; \ { \ ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \ ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \ while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \ VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \ found = true; \ break; \ } else { \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \ VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \ } else { \ VARIABLE_FOR_BINARY_SEARCH_U = ANSWER - 1; \ } \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ } \ } \ } \ template class BIT { private: T m_fenwick[N + 1]; public: inline BIT(); BIT( const T ( & a )[N] ); inline void Set( const int& i , const T& n ); inline BIT& operator+=( const T ( & a )[N] ); void Add( const int& i , const T& n ); T InitialSegmentSum( const int& i_final ); inline T IntervalSum( const int& i_start , const int& i_final ); }; template inline BIT::BIT() : m_fenwick() {} template BIT::BIT( const T ( & a )[N] ) : m_fenwick() { for( int j = 1 ; j <= N ; j++ ){ T& fenwick_j = m_fenwick[j]; int i = j - 1; fenwick_j = a[i]; int i_lim = j - ( j & -j ); while( i != i_lim ){ fenwick_j += m_fenwick[i]; i -= ( i & -i ); } } } template inline void BIT::Set( const int& i , const T& n ) { Add( i , n - IntervalSum( i , i ) ); } template inline BIT& BIT::operator+=( const T ( & a )[N] ) { for( int i = 0 ; i < N ; i++ ){ Add( i , a[i] ); } return *this; } template void BIT::Add( const int& i , const T& n ) { int j = i + 1; while( j <= N ){ m_fenwick[j] += n; j += ( j & -j ); } return; } template T BIT::InitialSegmentSum( const int& i_final ) { T sum = 0; int j = ( i_final < N ? i_final : N - 1 ) + 1; while( j > 0 ){ sum += m_fenwick[j]; j -= j & -j; } return sum; } template inline T BIT::IntervalSum( const int& i_start , const int& i_final ) { return InitialSegmentSum( i_final ) - InitialSegmentSum( i_start - 1 ); } template class IntervalAddBIT { private: // 母関数の微分の負の階差数列((i-1)a_{i-1} - ia_i)の管理 BIT m_bit_0; // 階差数列(a_i - a_{i-1})の管理 BIT m_bit_1; public: inline IntervalAddBIT(); inline IntervalAddBIT( const T ( & a )[N] ); inline void Set( const int& i , const T& n ); inline IntervalAddBIT& operator+=( const T ( & a )[N] ); inline void Add( const int& i , const T& n ); inline void IntervalAdd( const int& i_start , const int& i_final , const T& n ); inline T InitialSegmentSum( const int& i_final ); inline T IntervalSum( const int& i_start , const int& i_final ); }; template inline IntervalAddBIT::IntervalAddBIT() : m_bit_0() , m_bit_1() {} template inline IntervalAddBIT::IntervalAddBIT( const T ( & a )[N] ) : m_bit_0() , m_bit_1() { operator+=( a ); } template inline void IntervalAddBIT::Set( const int& i , const T& n ) { Add( i , n - IntervalSum( i , i ) ); } template inline IntervalAddBIT& IntervalAddBIT::operator+=( const T ( & a )[N] ) { for( int i = 0 ; i < N ; i++ ){ Add( i , a[i] ); } return *this; } template inline void IntervalAddBIT::Add( const int& i , const T& n ) { IntervalAdd( i , i , n ); } template inline void IntervalAddBIT::IntervalAdd( const int& i_start , const int& i_final , const T& n ) { m_bit_0.Add( i_start , - ( i_start - 1 ) * n ); m_bit_0.Add( i_final + 1 , i_final * n ); m_bit_1.Add( i_start , n ); m_bit_1.Add( i_final + 1 , - n ); } template inline T IntervalAddBIT::InitialSegmentSum( const int& i_final ) { return m_bit_0.InitialSegmentSum( i_final ) + i_final * m_bit_1.InitialSegmentSum( i_final ); } template inline T IntervalAddBIT::IntervalSum( const int& i_start , const int& i_final ) { return InitialSegmentSum( i_final ) - InitialSegmentSum( i_start - 1 ); } int MAIN() { UNTIE; CEXPR( int , bound_Q , 100000 ); CIN_ASSERT( Q , 1 , bound_Q ); CEXPR( ll , bound , 1000000000 ); ll KM[bound_Q][2]; ll LN[bound_Q][2]; ll X[bound_Q]; map X_inv{}; X_inv[-bound-1]; X_inv[bound+1]; FOR( q , 0 , Q ){ CIN_ASSERT( Kq , -bound , bound ); CIN_ASSERT( Lq , -bound , bound ); CIN_ASSERT( Mq , -bound , bound ); CIN_ASSERT( Nq , -bound , bound ); CIN_ASSERT( Xq , -bound , bound ); ll ( &KMq )[2] = KM[q]; ll ( &LNq )[2] = LN[q]; KMq[0] = Kq; LNq[0] = Lq; KMq[1] = Mq; LNq[1] = Nq; X_inv[X[q] = Xq]; } ll TheAtsuX[bound_Q+2]; int i_max = -1; FOR_ITR( X_inv , itr , end ){ TheAtsuX[itr->second = ++i_max] = itr->first; } IntervalAddBIT FGL[2][2] = {}; IntervalAddBIT FGR[2][2] = {}; FOR( q , 0 , Q ){ ll ( &KMq )[2] = KM[q]; ll ( &LNq )[2] = LN[q]; FOR( j , 0 , 2 ){ ll& KMqj = KMq[j]; ll& LNqj = LNq[j]; IntervalAddBIT ( &FGLj )[2] = FGL[j]; IntervalAddBIT ( &FGRj )[2] = FGR[j]; if( KMqj == 0 ){ if( LNqj > 0 ){ FGLj[0].IntervalAdd( 0 , i_max , LNqj ); FGRj[0].IntervalAdd( 0 , i_max , LNqj ); } } else if( KMqj > 0 ){ bool found = false; BS1( i , 0 , i_max , KMqj * TheAtsuX[i] + LNqj , 0 ); if( found ){ FGLj[0].IntervalAdd( i + 1 , i_max , LNqj ); FGLj[1].IntervalAdd( i + 1 , i_max , KMqj ); } else { FGLj[0].IntervalAdd( i , i_max , LNqj ); FGLj[1].IntervalAdd( i , i_max , KMqj ); } FGRj[0].IntervalAdd( i , i_max , LNqj ); FGRj[1].IntervalAdd( i , i_max , KMqj ); } else { bool found = false; BS3( i , 0 , i_max , KMqj * TheAtsuX[i] + LNqj , 0 ); if( found ){ FGRj[0].IntervalAdd( 0 , i - 1 , LNqj ); FGRj[1].IntervalAdd( 0 , i - 1 , KMqj ); } else { FGRj[0].IntervalAdd( 0 , i , LNqj ); FGRj[1].IntervalAdd( 0 , i , KMqj ); } FGLj[0].IntervalAdd( 0 , i , LNqj ); FGLj[1].IntervalAdd( 0 , i , KMqj ); } } IntervalAddBIT ( &FL )[2] = FGL[0]; IntervalAddBIT ( &FR )[2] = FGR[0]; IntervalAddBIT ( &GL )[2] = FGL[1]; IntervalAddBIT ( &GR )[2] = FGR[1]; int& i = X_inv[X[q]]; if( FL[0].IntervalSum( i , i ) == GL[0].IntervalSum( i , i ) && FL[1].IntervalSum( i , i ) == GL[1].IntervalSum( i , i ) && FR[1].IntervalSum( i , i ) == GR[1].IntervalSum( i , i ) ){ COUT( "Yes" ); } else { COUT( "No" ); } } QUIT; }