// 一次関数の代わりに割り算を用いた比較 // 何故か実行のたびに実行時間がものすごく変わる(228〜345[ms]) #ifdef DEBUG #define _GLIBCXX_DEBUG #define REPEAT_MAIN( BOUND ) START_MAIN; signal( SIGABRT , &AlertAbort ); AutoCheck( exec_mode ); if( exec_mode == debug_mode || exec_mode == library_search_mode ){ return 0; } else if( exec_mode == experiment_mode ){ Experiment(); return 0; } else if( exec_mode == small_test_mode ){ SmallTest(); return 0; }; DEXPR( int , bound_test_case_num , BOUND , min( BOUND , 100 ) ); int test_case_num = 1; if( exec_mode == solve_mode ){ if constexpr( bound_test_case_num > 1 ){ SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } } else if( exec_mode == random_test_mode ){ CERR( "ランダムテストを行う回数を指定してください。" ); cin >> test_case_num; } FINISH_MAIN #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE ) #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック: " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) ) #define SET_ASSERT( A , MIN , MAX ) if( exec_mode == solve_mode ){ cin >> A; ASSERT( A , MIN , MAX ); } else if( exec_mode == random_test_mode ){ CERR( #A , " = " , ( A = GetRand( MIN , MAX ) ) ); } else { assert( false ); } #define SOLVE_ONLY static_assert( __FUNCTION__[0] == 'S' ) #define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl #define COUT( ... ) VariadicCout( cout << "出力: " , __VA_ARGS__ ) << endl #define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl #define COUT_A( A , N ) cout << "出力: "; OUTPUT_ARRAY( cout , A , N ) << endl #define CERR_ITR( A ) OUTPUT_ITR( cerr , A ) << endl #define COUT_ITR( A ) cout << "出力: "; OUTPUT_ITR( cout , A ) << endl #else #pragma GCC optimize ( "O3" ) #pragma GCC optimize ( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #define REPEAT_MAIN( BOUND ) START_MAIN; CEXPR( int , bound_test_case_num , BOUND ); int test_case_num = 1; if constexpr( bound_test_case_num > 1 ){ SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } FINISH_MAIN #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE ) #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX ) #define SOLVE_ONLY #define CERR( ... ) #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << "\n" #define CERR_A( A , N ) #define COUT_A( A , N ) OUTPUT_ARRAY( cout , A , N ) << "\n" #define CERR_ITR( A ) #define COUT_ITR( A ) OUTPUT_ITR( cout , A ) << "\n" #endif #include using namespace std; using uint = unsigned int; using ll = long long; using ull = unsigned long long; #define START_MAIN int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define FINISH_MAIN REPEAT( test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); } Solve(); CERR( "" ); } } #define TYPE_OF( VAR ) decay_t #define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE #define CIN( LL , ... ) SOLVE_ONLY; LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ ) #define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_ASSERT( A , MIN , MAX ) #define SET_A( A , N ) SOLVE_ONLY; FOR( VARIABLE_FOR_CIN_A , 0 , N ){ cin >> A[VARIABLE_FOR_CIN_A]; } #define CIN_A( LL , A , N ) vector A( N ); SET_A( A , N ); #define GETLINE_SEPARATE( SEPARATOR , ... ) SOLVE_ONLY; string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ ) #define GETLINE( ... ) SOLVE_ONLY; GETLINE_SEPARATE( '\n' , __VA_ARGS__ ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- ) #define AUTO_ITR( ARRAY ) auto itr_ ## ARRAY = ARRAY .begin() , end_ ## ARRAY = ARRAY .end() #define FOR_ITR( ARRAY ) for( AUTO_ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES ) #define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS ) #define OUTPUT_ARRAY( OS , A , N ) FOR( VARIABLE_FOR_OUTPUT_ARRAY , 0 , N ){ OS << A[VARIABLE_FOR_OUTPUT_ARRAY] << (VARIABLE_FOR_OUTPUT_ARRAY==N-1?"":" "); } OS #define OUTPUT_ITR( OS , A ) { auto ITERATOR_FOR_OUTPUT_ITR = A.begin() , END_FOR_OUTPUT_ITR = A.end(); bool VARIABLE_FOR_OUTPUT_ITR = ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR; while( VARIABLE_FOR_OUTPUT_ITR ){ OS << *ITERATOR_FOR_COUT_ITR; ( VARIABLE_FOR_OUTPUT_ITR = ++ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR ) ? OS : OS << " "; } } OS #define RETURN( ... ) SOLVE_ONLY; COUT( __VA_ARGS__ ); return #define COMPARE( ... ) auto naive = Naive( __VA_ARGS__ ); auto answer = Answer( __VA_ARGS__ ); bool match = naive == answer; COUT( #__VA_ARGS__ , ":" , naive , match ? "==" : "!=" , answer ); if( !match ){ return; } // 入出力用 template inline basic_istream& VariadicCin( basic_istream& is ) { return is; } template inline basic_istream& VariadicCin( basic_istream& is , Arg& arg , ARGS&... args ) { return VariadicCin( is >> arg , args... ); } template inline basic_istream& VariadicGetline( basic_istream& is , const char& separator ) { return is; } template inline basic_istream& VariadicGetline( basic_istream& is , const char& separator , Arg& arg , ARGS&... args ) { return VariadicGetline( getline( is , arg , separator ) , separator , args... ); } template inline basic_ostream& VariadicCout( basic_ostream& os , const Arg& arg ) { return os << arg; } template inline basic_ostream& VariadicCout( basic_ostream& os , const Arg1& arg1 , const Arg2& arg2 , const ARGS&... args ) { return VariadicCout( os << arg1 << " " , arg2 , args... ); } // 算術用 template constexpr T PositiveBaseResidue( const T& a , const T& p ){ return a >= 0 ? a % p : p - 1 - ( ( - ( a + 1 ) ) % p ); } template constexpr T Residue( const T& a , const T& p ){ return PositiveBaseResidue( a , p < 0 ? -p : p ); } template constexpr T PositiveBaseQuotient( const T& a , const T& p ){ return ( a - PositiveBaseResidue( a , p ) ) / p; } template constexpr T Quotient( const T& a , const T& p ){ return p < 0 ? PositiveBaseQuotient( -a , -p ) : PositiveBaseQuotient( a , p ); } // 二分探索テンプレート // EXPRESSIONがANSWERの広義単調関数の時、EXPRESSION >= TARGETの整数解を格納。 #define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , DESIRED_INEQUALITY , TARGET , INEQUALITY_FOR_CHECK , UPDATE_U , UPDATE_L , UPDATE_ANSWER ) \ static_assert( ! is_same::value && ! is_same::value ); \ ll ANSWER = MINIMUM; \ ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \ ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \ ANSWER = UPDATE_ANSWER; \ 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 ); \ CERR( "二分探索中:" , VARIABLE_FOR_BINARY_SEARCH_L , "<=" , ANSWER , "<=" , VARIABLE_FOR_BINARY_SEARCH_U , ":" , EXPRESSION , "-" , TARGET , "=" , VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH INEQUALITY_FOR_CHECK 0 ){ \ VARIABLE_FOR_BINARY_SEARCH_U = UPDATE_U; \ } else { \ VARIABLE_FOR_BINARY_SEARCH_L = UPDATE_L; \ } \ ANSWER = UPDATE_ANSWER; \ } \ if( VARIABLE_FOR_BINARY_SEARCH_L > VARIABLE_FOR_BINARY_SEARCH_U ){ \ CERR( "二分探索失敗:" , VARIABLE_FOR_BINARY_SEARCH_L , ">" , VARIABLE_FOR_BINARY_SEARCH_U ); \ ANSWER = MAXIMUM + 1; \ } else { \ CERR( "二分探索終了:" , VARIABLE_FOR_BINARY_SEARCH_L , "<=" , ANSWER , "<=" , VARIABLE_FOR_BINARY_SEARCH_U , ":" , EXPRESSION , ( EXPRESSION > TARGET ? ">" : EXPRESSION < TARGET ? "<" : "=" ) , TARGET ); \ if( EXPRESSION DESIRED_INEQUALITY TARGET ){ \ CERR( "二分探索成功:" , #ANSWER , "=" , ANSWER ); \ } else { \ CERR( "二分探索失敗:" , EXPRESSION , "<>"[EXPRESSION > TARGET], TARGET ); \ ANSWER = MAXIMUM + 1; \ } \ } \ // 単調増加の時にEXPRESSION >= TARGETの最小解を格納。 #define BS1( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , >= , TARGET , >= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \ // 単調増加の時にEXPRESSION <= TARGETの最大解を格納。 #define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , <= , TARGET , > , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \ // 単調減少の時にEXPRESSION >= TARGETの最大解を格納。 #define BS3( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , >= , TARGET , < , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \ // 単調減少の時にEXPRESSION <= TARGETの最小解を格納。 #define BS4( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , <= , TARGET , <= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \ // デバッグ用 #ifdef DEBUG inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); } void AutoCheck( int& exec_mode ); inline void Solve(); inline void Experiment(); inline void SmallTest(); inline void RandomTest(); ll GetRand( const ll& Rand_min , const ll& Rand_max ); int exec_mode; CEXPR( int , solve_mode , 0 ); CEXPR( int , debug_mode , 1 ); CEXPR( int , library_search_mode , 2 ); CEXPR( int , experiment_mode , 3 ); CEXPR( int , small_test_mode , 4 ); CEXPR( int , random_test_mode , 5 ); #endif 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 ); } inline void Solve() { DEXPR( int , bound_Q , 100000 , 100 ); 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 ){ 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 ){ ll div = -Quotient( LNqj , KMqj ); BS1( i , 0 , i_max , TheAtsuX[i] , div ); if( LNqj % KMqj == 0 && TheAtsuX[i] == -LNqj / KMqj ){ 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 { ll div = Quotient( LNqj , -KMqj ); BS2( i , 0 , i_max , TheAtsuX[i] , div ); if( LNqj % KMqj == 0 && TheAtsuX[i] == - LNqj / KMqj ){ FGLj[0].IntervalAdd( 0 , i - 1 , LNqj ); FGLj[1].IntervalAdd( 0 , i - 1 , KMqj ); } else { FGLj[0].IntervalAdd( 0 , i , LNqj ); FGLj[1].IntervalAdd( 0 , i , KMqj ); } FGRj[0].IntervalAdd( 0 , i , LNqj ); FGRj[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" ); } } } inline void Experiment() { // CEXPR( int , bound , 10 ); // FOREQ( N , 0 , bound ){ // FOREQ( M , 0 , bound ){ // FOREQ( K , 0 , bound ){ // COUT( N , M , K , ":" , Naive( N , M , K ) ); // } // } // // cout << Naive( N ) << ",\n"[N==bound]; // } } inline void SmallTest() { // CEXPR( int , bound , 10 ); // FOREQ( N , 0 , bound ){ // FOREQ( M , 0 , bound ){ // FOREQ( K , 0 , bound ){ // COMPARE( N , M , K ); // } // } // // COMPARE( N ); // } } REPEAT_MAIN(1);