結果
問題 | No.2974 関数の芽 |
ユーザー | 👑 p-adic |
提出日時 | 2023-03-20 20:01:33 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 347 ms / 2,000 ms |
コード長 | 9,569 bytes |
コンパイル時間 | 3,740 ms |
コンパイル使用メモリ | 236,804 KB |
実行使用メモリ | 26,908 KB |
最終ジャッジ日時 | 2024-09-22 19:29:29 |
合計ジャッジ時間 | 8,015 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
16,000 KB |
testcase_01 | AC | 6 ms
15,872 KB |
testcase_02 | AC | 6 ms
16,000 KB |
testcase_03 | AC | 6 ms
16,128 KB |
testcase_04 | AC | 7 ms
16,000 KB |
testcase_05 | AC | 6 ms
16,128 KB |
testcase_06 | AC | 7 ms
16,000 KB |
testcase_07 | AC | 6 ms
16,000 KB |
testcase_08 | AC | 6 ms
16,000 KB |
testcase_09 | AC | 7 ms
16,000 KB |
testcase_10 | AC | 7 ms
16,128 KB |
testcase_11 | AC | 6 ms
16,000 KB |
testcase_12 | AC | 8 ms
16,000 KB |
testcase_13 | AC | 21 ms
16,384 KB |
testcase_14 | AC | 150 ms
19,800 KB |
testcase_15 | AC | 311 ms
26,908 KB |
testcase_16 | AC | 163 ms
26,828 KB |
testcase_17 | AC | 281 ms
26,752 KB |
testcase_18 | AC | 279 ms
26,880 KB |
testcase_19 | AC | 303 ms
26,872 KB |
testcase_20 | AC | 278 ms
26,852 KB |
testcase_21 | AC | 298 ms
26,880 KB |
testcase_22 | AC | 306 ms
26,800 KB |
testcase_23 | AC | 347 ms
26,880 KB |
ソースコード
#pragma GCC optimize ( "O3" ) #pragma GCC optimize( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #include<bits/stdc++.h> using namespace std; using ll = long long; #define MAIN main #define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::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 <typename T , int N> 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<T,N>& 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 <typename T , int N> inline BIT<T,N>::BIT() : m_fenwick() {} template <typename T , int N> BIT<T,N>::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 <typename T , int N> inline void BIT<T,N>::Set( const int& i , const T& n ) { Add( i , n - IntervalSum( i , i ) ); } template <typename T , int N> inline BIT<T,N>& BIT<T,N>::operator+=( const T ( & a )[N] ) { for( int i = 0 ; i < N ; i++ ){ Add( i , a[i] ); } return *this; } template <typename T , int N> void BIT<T,N>::Add( const int& i , const T& n ) { int j = i + 1; while( j <= N ){ m_fenwick[j] += n; j += ( j & -j ); } return; } template <typename T , int N> T BIT<T,N>::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 <typename T , int N> inline T BIT<T,N>::IntervalSum( const int& i_start , const int& i_final ) { return InitialSegmentSum( i_final ) - InitialSegmentSum( i_start - 1 ); } template <typename T , int N> class IntervalAddBIT { private: // 母関数の微分の負の階差数列((i-1)a_{i-1} - ia_i)の管理 BIT<T,N> m_bit_0; // 階差数列(a_i - a_{i-1})の管理 BIT<T,N> m_bit_1; public: inline IntervalAddBIT(); inline IntervalAddBIT( const T ( & a )[N] ); inline void Set( const int& i , const T& n ); inline IntervalAddBIT<T,N>& 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 <typename T , int N> inline IntervalAddBIT<T,N>::IntervalAddBIT() : m_bit_0() , m_bit_1() {} template <typename T , int N> inline IntervalAddBIT<T,N>::IntervalAddBIT( const T ( & a )[N] ) : m_bit_0() , m_bit_1() { operator+=( a ); } template <typename T , int N> inline void IntervalAddBIT<T,N>::Set( const int& i , const T& n ) { Add( i , n - IntervalSum( i , i ) ); } template <typename T , int N> inline IntervalAddBIT<T,N>& IntervalAddBIT<T,N>::operator+=( const T ( & a )[N] ) { for( int i = 0 ; i < N ; i++ ){ Add( i , a[i] ); } return *this; } template <typename T , int N> inline void IntervalAddBIT<T,N>::Add( const int& i , const T& n ) { IntervalAdd( i , i , n ); } template <typename T , int N> inline void IntervalAddBIT<T,N>::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 <typename T , int N> inline T IntervalAddBIT<T,N>::InitialSegmentSum( const int& i_final ) { return m_bit_0.InitialSegmentSum( i_final ) + i_final * m_bit_1.InitialSegmentSum( i_final ); } template <typename T , int N> inline T IntervalAddBIT<T,N>::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<ll,int> 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<ll,bound_Q+2> FGL[2][2] = {}; IntervalAddBIT<ll,bound_Q+2> 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<ll,bound_Q+2> ( &FGLj )[2] = FGL[j]; IntervalAddBIT<ll,bound_Q+2> ( &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<ll,bound_Q+2> ( &FL )[2] = FGL[0]; IntervalAddBIT<ll,bound_Q+2> ( &FR )[2] = FGR[0]; IntervalAddBIT<ll,bound_Q+2> ( &GL )[2] = FGL[1]; IntervalAddBIT<ll,bound_Q+2> ( &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; }