#977286 (C++17) No.2161 Black Market

• 問題: No.2161 Black Market
• ユーザー: 👑 p-adic
• 提出日時: 2024-04-25 13:20:06
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 557 ms / 7,000 ms
• コード長: 10,208 bytes
• コンパイル時間: 3,108 ms
• コンパイル使用メモリ: 227,676 KB
• 実行使用メモリ: 26,368 KB
• 最終ジャッジ日時: 2024-11-08 00:23:12
• 合計ジャッジ時間: 5,800 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	3 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	3 ms; 5,248 KB
testcase_06	AC	4 ms; 5,248 KB
testcase_07	AC	5 ms; 5,248 KB
testcase_08	AC	5 ms; 5,248 KB
testcase_09	AC	4 ms; 5,248 KB
testcase_10	AC	5 ms; 5,248 KB
testcase_11	AC	4 ms; 5,248 KB
testcase_12	AC	3 ms; 5,248 KB
testcase_13	AC	3 ms; 5,248 KB
testcase_14	AC	3 ms; 5,248 KB
testcase_15	AC	5 ms; 5,248 KB
testcase_16	AC	3 ms; 5,248 KB
testcase_17	AC	2 ms; 5,248 KB
testcase_18	AC	2 ms; 5,248 KB
testcase_19	AC	3 ms; 5,248 KB
testcase_20	AC	9 ms; 5,248 KB
testcase_21	AC	9 ms; 5,248 KB
testcase_22	AC	10 ms; 5,248 KB
testcase_23	AC	10 ms; 5,248 KB
testcase_24	AC	557 ms; 26,368 KB
testcase_25	AC	154 ms; 24,320 KB
testcase_26	AC	472 ms; 26,368 KB
testcase_27	AC	9 ms; 5,248 KB
testcase_28	AC	20 ms; 7,040 KB
testcase_29	AC	17 ms; 6,400 KB
testcase_30	AC	22 ms; 5,248 KB
testcase_31	AC	290 ms; 22,272 KB
testcase_32	AC	3 ms; 5,248 KB
testcase_33	AC	45 ms; 6,272 KB
testcase_34	AC	3 ms; 5,248 KB
testcase_35	AC	3 ms; 5,248 KB
testcase_36	AC	5 ms; 5,248 KB
testcase_37	AC	6 ms; 5,248 KB
testcase_38	AC	7 ms; 5,248 KB
testcase_39	AC	4 ms; 5,248 KB

ソースコード

#pragma GCC optimize ( "O3" )
//#pragma GCC target ( "avx" )
#include <bits/stdc++.h>
using namespace std;

using uint = unsigned int;
using ll = long long;

#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 GETLINE( A ) string A; getline( cin , A ) 
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) 
#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 FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) 
#define QUIT return 0 
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"; 
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT 
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << "\n"; QUIT 

#define POWER( ANSWER , ARGUMENT , EXPONENT )				\
  TYPE_OF( ARGUMENT ) ANSWER{ 1 };					\
  {									\
    TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT );	\
    TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT );	\
    while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){			\
      if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){			\
	ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER;			\
      }									\
      ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER;	\
      EXPONENT_FOR_SQUARE_FOR_POWER /= 2;				\
    }									\
  }									\


#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO )		\
  TYPE_OF( ARGUMENT ) ANSWER{ 1 };					\
  {									\
    TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ARGUMENT ) % MODULO ) % MODULO; \
    TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT );	\
    while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){			\
      if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){			\
	ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO;	\
      }									\
      ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
      EXPONENT_FOR_SQUARE_FOR_POWER /= 2;				\
    }									\
  }									\


#define FACTORIAL_MOD( ANSWER , ANSWER_INV , MAX_I , LENGTH , MODULO )	\
  ll ANSWER[LENGTH];							\
  ll ANSWER_INV[LENGTH];						\
  {									\
    ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1;				\
    ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL;			\
    FOREQ( i , 1 , MAX_I ){						\
      ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= MODULO; \
    }									\
    POWER_MOD( FACTORIAL_MAX_INV , ANSWER[MAX_I] , MODULO - 2 , MODULO ); \
    ANSWER_INV[MAX_I] = FACTORIAL_MAX_INV;				\
    FOREQINV( i , MAX_I - 1 , 0 ){					\
      ANSWER_INV[i] = ( FACTORIAL_MAX_INV *= i + 1 ) %= MODULO;		\
    }									\
  }									\
									\

// 通常の二分探索
#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  ll ANSWER = MAXIMUM;							\
  {									\
    ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM;				\
    ll VARIABLE_FOR_BINARY_SEARCH_U = ANSWER;				\
    ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
    if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){		\
      VARIABLE_FOR_BINARY_SEARCH_L = ANSWER;				\
    } else {								\
      ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
    }									\
    while( VARIABLE_FOR_BINARY_SEARCH_L != ANSWER ){			\
      VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
      if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){		\
	VARIABLE_FOR_BINARY_SEARCH_L = ANSWER;				\
	break;								\
      } else {								\
	if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){		\
	  VARIABLE_FOR_BINARY_SEARCH_L = ANSWER;			\
	} else {							\
	  VARIABLE_FOR_BINARY_SEARCH_U = ANSWER;			\
	}								\
	ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
      }									\
    }									\
  }									\
									\


// 二進法の二分探索
#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  ll ANSWER = MINIMUM;							\
  {									\
    ll VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 = 1;			\
    ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( MAXIMUM ) - ANSWER; \
    while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 <= VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ){ \
      VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 *= 2;			\
    }									\
    VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2;			\
    ll VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER;		\
    while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 != 0 ){		\
      ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 + VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2; \
      VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
      if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){		\
	VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER;		\
	break;								\
      } else if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){	\
	VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER;		\
      }									\
      VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2;			\
    }									\
    ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2;			\
  }									\
									\


template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : - a; }
template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : p - ( - a - 1 ) % p - 1; }


//  InitialSegmentSumで負の入力を扱うためにuintではなくintをテンプレート引数にする。
template <typename T , int N>
class BIT
{
private:
  T m_fenwick[N + 1];

public:
  inline BIT();
  inline 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> inline BIT<T,N>::BIT( const T ( & a )[N] ) : m_fenwick() { operator+=( a ); }

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 ); }


#define MULTIPLICATION( F0 , SIGN )		\
  {						\
    FOR( i , 0 , N_half ){			\
      CIN_ASSERT( Ai , 1 , bound );		\
      CIN_ASSERT( Bi , 1 , bound );		\
      FOREQINV( d0 , min( K , i ) , 0 ){	\
	map<pair<int,int>,int>& fd0 = F0[d0];	\
	map<pair<int,int>,int>& fd1 = F0[d0+1];	\
	FOR_ITR( fd0 , itr , end ){		\
	  l0 = itr->first.second;		\
	  l1 = l0 + Ai;				\
	  if( l1 <= L ){			\
	    p0 = itr->first.first;		\
	    p1 = p0 + ( SIGN ) * Bi;		\
	    if( ( SIGN ) * p1 > P ){		\
	      p1 = ( SIGN ) * P;		\
	    }					\
	    fd1[c1] += fd0[c0];			\
	  }					\
	}					\
      }						\
    }						\
  }						\
						\

int main()
{
  UNTIE;
  CEXPR( int , bound_N , 34 );
  CIN_ASSERT( N , 1 , bound_N );
  CIN_ASSERT( K , 1 , N );
  CEXPR( int , bound , 1000000000 );
  CIN_ASSERT( L , 1 , bound );
  CIN_ASSERT( P , 1 , bound );
  pair<int,int> c0{};
  pair<int,int> c1{};
  int& p0 = c0.first;
  int& l0 = c0.second;
  int& p1 = c1.first;
  int& l1 = c1.second;
  CEXPR( int , bound_N_half , bound_N / 2);
  map<pair<int,int>,int> f[2][bound_N_half + 1] = {};
  map<pair<int,int>,int> ( &f0 )[bound_N_half + 1] = f[0];
  map<pair<int,int>,int> ( &f1 )[bound_N_half + 1] = f[1];
  f0[0][c1] = 1;
  f1[0][c1] = 1;
  int N_half = N / 2;
  MULTIPLICATION( f0 , 1 );
  int K0 = min( K , N_half );
  N_half = N - N_half;
  MULTIPLICATION( f1 , -1 );
  int K1 = min( K , N_half );
  map<int,int> TheAtl1[bound_N_half + 1] = {};
  int num;
  FOREQ( d1 , 0 , K1 ){
    map<pair<int,int>,int>& f1d1 = f1[d1];
    map<int,int>& TheAtl1d1 = TheAtl1[d1];
    FOR_ITR( f1d1 , itr1 , end1 ){
      TheAtl1d1[- itr1->first.second] = 0;
    }
    num = 0;
    FOR_ITR( TheAtl1d1 , itr1 , end1 ){
      itr1->second = num++;
    }
  }
  ll answer = 0;
  map<int,int>::iterator itr_TheAtl1d1 , end_TheAtl1d1;
  map<pair<int,int>,int>::iterator itr1 , end1;
  CEXPR( int , length , 1 << bound_N_half );
  FOREQINV( d0 , K0 , 0 ){
    map<pair<int,int>,int>& f0d0 = f0[d0];
    FOREQINV( d1 , min( K1 , K - d0 ) , 0 ){
      map<pair<int,int>,int>& f1d1 = f1[d1];
      map<int,int>& TheAtl1d1 = TheAtl1[d1];
      BIT<int,length> S{};
      itr1 = f1d1.begin();
      end1 = f1d1.end();
      end_TheAtl1d1 = TheAtl1d1.end();
      c1 = itr1->first;
      FOR_ITR( f0d0 , itr0 , end0 ){
	c0 = itr0->first;
	while( itr1 != end1 && p0 - p1 >= P ){
	  S.Add( TheAtl1d1[- c1.second] , itr1->second );
	  itr1++;
	  c1 = itr1->first;
	}
	itr_TheAtl1d1 = TheAtl1d1.lower_bound( l0 - L );
	if( itr_TheAtl1d1 != end_TheAtl1d1 ){
	  num = itr_TheAtl1d1->second;
	  answer += itr0->second * S.IntervalSum( num , length - 1 );
	}
      }
    }
  }
  RETURN( answer );
}