#895356 (C++17) No.2650 [Cherry 6th Tune *] セイジャク

提出ソース

結果

問題	No.2650 [Cherry 6th Tune *] セイジャク
ユーザー	👑 p-adic
提出日時	2023-07-26 13:58:45
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	546 ms / 2,500 ms
コード長	14,229 bytes
コンパイル時間	1,422 ms
コンパイル使用メモリ	93,788 KB
実行使用メモリ	22,276 KB
最終ジャッジ日時	2024-11-15 05:37:13
合計ジャッジ時間	14,918 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 6,888 KB
testcase_01	AC	4 ms 7,008 KB
testcase_02	AC	77 ms 10,604 KB
testcase_03	AC	38 ms 9,588 KB
testcase_04	AC	347 ms 18,156 KB
testcase_05	AC	240 ms 15,340 KB
testcase_06	AC	95 ms 11,816 KB
testcase_07	AC	272 ms 16,360 KB
testcase_08	AC	63 ms 10,296 KB
testcase_09	AC	546 ms 22,120 KB
testcase_10	AC	539 ms 22,128 KB
testcase_11	AC	524 ms 22,128 KB
testcase_12	AC	525 ms 22,248 KB
testcase_13	AC	512 ms 22,104 KB
testcase_14	AC	518 ms 22,124 KB
testcase_15	AC	519 ms 22,116 KB
testcase_16	AC	469 ms 22,128 KB
testcase_17	AC	457 ms 22,128 KB
testcase_18	AC	464 ms 22,124 KB
testcase_19	AC	474 ms 22,276 KB
testcase_20	AC	473 ms 22,116 KB
testcase_21	AC	476 ms 22,124 KB
testcase_22	AC	484 ms 22,128 KB
testcase_23	AC	279 ms 22,132 KB
testcase_24	AC	275 ms 22,252 KB
testcase_25	AC	282 ms 22,244 KB
testcase_26	AC	277 ms 22,116 KB
testcase_27	AC	288 ms 22,128 KB
testcase_28	AC	284 ms 22,252 KB
testcase_29	AC	285 ms 22,120 KB
testcase_30	AC	389 ms 22,128 KB
testcase_31	AC	279 ms 22,244 KB
testcase_32	AC	146 ms 12,404 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ); signal( SIGABRT , &AlertAbort )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
  #define CERR( ANSWER ) cerr << ANSWER << endl;
  #define COUT( ANSWER ) cout << ANSWER << endl
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " << ( MIN ) << ( ( MIN ) <= A ? "<=" : ">" ) << A << ( A <= ( MAX ) ? "<=" : ">" ) << ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
  #define LIBRARY_SEARCH if( LibrarySearch() != 0 ){ QUIT; };
  #define START_WATCH( PROCESS_NAME ) StartWatch( PROCESS_NAME )
  #define STOP_WATCH( HOW_MANY_TIMES ) StopWatch( HOW_MANY_TIMES )
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
  #define CERR( ANSWER ) 
  #define COUT( ANSWER ) cout << ANSWER << "\n"
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
  #define LIBRARY_SEARCH
  #define START_WATCH( PROCESS_NAME )
  #define STOP_WATCH( HOW_MANY_TIMES )
#endif
#include <iostream>
#include <map>
#include <cassert>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define SET_ASSERT( A , MIN , MAX ) cin >> 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 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 QUIT return 0
#define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS_ )
#define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT

#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
  void StartWatch( const string& process_name = "nothing" );
  void StopWatch( const int& how_many_times = 1 );
#endif

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 - 1 - ( ( - ( a + 1 ) ) % p ); }

// 入力フォーマットチェック用
// 1行中の変数の個数を確認
#define GETLINE_COUNT( S , VARIABLE_NUMBER ) GETLINE( S ); int VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S = 0; int VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S  = S.size(); { int size = S.size(); int count = 0; for( int i = 0 ; i < size ; i++ ){ if( S.substr( i , 1 ) == " " ){ count++; } } assert( count + 1 == VARIABLE_NUMBER ); }
// 余計な入力の有無を確認
#ifdef DEBUG
  #define CHECK_REDUNDANT_INPUT 
#else
  #define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; cin >> VARIABLE_FOR_CHECK_REDUNDANT_INPUT; assert( VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin )
  // #define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; getline( cin , VARIABLE_FOR_CHECK_REDUNDANT_INPUT ); assert( VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin )
#endif
// |N| <= BOUNDを満たすNをSから構築
#define STOI( S , N , BOUND ) TYPE_OF( BOUND ) N = 0; { bool VARIABLE_FOR_POSITIVITY_FOR_GETLINE = true; assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); if( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) == "-" ){ VARIABLE_FOR_POSITIVITY_FOR_GETLINE = false; VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); } assert( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) != " " ); string VARIABLE_FOR_LETTER_FOR_GETLINE{}; int VARIABLE_FOR_DIGIT_FOR_GETLINE{}; while( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ? ( VARIABLE_FOR_LETTER_FOR_GETLINE = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) ) != " " : false ){ VARIABLE_FOR_DIGIT_FOR_GETLINE = stoi( VARIABLE_FOR_LETTER_FOR_GETLINE ); assert( N < BOUND / 10 ? true : N == BOUND / 10 && VARIABLE_FOR_DIGIT_FOR_GETLINE <= BOUND % 10 ); N = N * 10 + VARIABLE_FOR_DIGIT_FOR_GETLINE; VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } if( ! VARIABLE_FOR_POSITIVITY_FOR_GETLINE ){ N *= -1; } if( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } }
// SをSEPARATORで区切りTを構築
#define SEPARATE( S , T , SEPARATOR ) string T{}; { assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); int VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev = VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S; assert( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) != SEPARATOR ); string VARIABLE_FOR_LETTER_FOR_GETLINE{}; while( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ? ( VARIABLE_FOR_LETTER_FOR_GETLINE = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) ) != SEPARATOR : false ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } T = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev , VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S - VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev ); if( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } }

template <int N>
class SqrtCalculation
{
public:
  int m_val;
  inline constexpr SqrtCalculation();
};

template <int N> inline constexpr SqrtCalculation<N>::SqrtCalculation() : m_val( 1 ) { int m_val2 = 1; while( ( m_val2 << 2 ) <= N ){ m_val <<= 1; m_val2 <<= 2; } while( m_val2 < N ){ m_val++; m_val2 = m_val * m_val; } }

#define TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION typename T , T m_T(const T&,const T&) , const T& e_T() , typename U , U o_U(const T&,const U&) , int N , int N_sqrt

// （結合的とも単位的とも限らない）基点付き可換マグマ(T,m_T:T^2->T,e_T:1->T)と基点が恒等変換に対応するT作用付き集合(U,o_U:T×U->U)と非負整数Nをパラメータとする。
// 配列による初期化O(N)

// 一点取得O(1)（可換性を使う）

// 一点更新O(N^{1/2})（可換性を使う。ただし状況次第でO(1)）
// o_Uによる一点更新O(1)（可換性を使う）
// o_Uによる区間更新O(min(i_final-i_start+1,N^{1/2}))（可換性を使う）
template <TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION = SqrtCalculation<N>{}.m_val >
class DualSqrtDecomposition
{

private:
  static constexpr const int N_d = ( N + N_sqrt - 1 ) / N_sqrt;
  static constexpr const int N_m = N_d * N_sqrt;
  U m_a[N_m];
  T m_b[N_d];

public:
  static const T& g_e;
  
  inline constexpr DualSqrtDecomposition( const U ( &a )[N] );

  inline constexpr U Get( const int& i ) const;
  inline constexpr void Set( const int& i , const U& u );

  inline constexpr void Act( const int& i , const T& t );
  inline constexpr void IntervalAct( const int& i_start , const int& i_final , const T& t );

private:
  inline constexpr void IntervalAct_Body( const int& i_min , const int& i_ulim , const T& t );
  
};

template <TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION> const T& DualSqrtDecomposition<T,m_T,e_T,U,o_U,N,N_sqrt>::g_e = e_T();

template <TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION> inline constexpr DualSqrtDecomposition<T,m_T,e_T,U,o_U,N,N_sqrt>::DualSqrtDecomposition( const U ( &a )[N] ) : m_a() , m_b() { if( m_b[0] != g_e ){ for( int d = 0 ; d < N_d ; d++ ){ m_b[d] = g_e; } } for( int i = 0 ; i < N ; i++ ){ m_a[i] = a[i]; } }

template <TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION> inline constexpr U DualSqrtDecomposition<T,m_T,e_T,U,o_U,N,N_sqrt>::Get( const int& i ) const { return o_U( m_b[i/N_sqrt] , m_a[i] ); }

template <TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION> inline constexpr void DualSqrtDecomposition<T,m_T,e_T,U,o_U,N,N_sqrt>::Set( const int& i , const U& u )
{

  U& m_ai = m_a[i];

  if( m_ai != u ){
    
    const int d = i / N_sqrt;
    T& m_bd = m_b[d];

    if( m_bd != g_e ){

      const int i_min = d * N_sqrt;
      IntervalAct_Body( i_min , i_min + N_sqrt , m_bd );
      m_bd = g_e;

    }

    m_ai = u;

  }

  return;

}

template <TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION> inline constexpr void DualSqrtDecomposition<T,m_T,e_T,U,o_U,N,N_sqrt>::Act( const int& i , const T& t ) { T& m_ai = m_a[i]; m_ai = o_U( t , m_ai ); }
template <TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION> inline constexpr void DualSqrtDecomposition<T,m_T,e_T,U,o_U,N,N_sqrt>::IntervalAct( const int& i_start , const int& i_final , const T& t )
{

  if( t != g_e ){
  
    const int i_min = max( i_start , 0 );
    const int i_ulim = min( i_final + 1 , N );
    const int d_0 = ( i_min + N_sqrt - 1 ) / N_sqrt;
    const int d_1 = max( d_0 , i_ulim / N_sqrt );
    const int i_0 = min( d_0 * N_sqrt , i_ulim );
    const int i_1 = max( i_0 , d_1 * N_sqrt );
    IntervalAct_Body( i_min , i_0 , t );
  
    for( int d = d_0 ; d < d_1 ; d++ ){

      T& m_bd = m_b[d];
      m_bd = m_T( t , m_bd );

    }

    IntervalAct_Body( i_1, i_ulim , t );

  }
  
  return;
  
}

template <TEMPLATE_ARGUMENTS_FOR_DUAL_SQRT_DECOMPOSITION> inline constexpr void DualSqrtDecomposition<T,m_T,e_T,U,o_U,N,N_sqrt>::IntervalAct_Body( const int& i_min , const int& i_ulim , const T& t )
{

  for( int i = i_min ; i < i_ulim ; i++ ){

    U& m_ai = m_a[i];
    m_ai = o_U( t , m_ai );

  }

  return;
  
}

inline int max_int( const int& t0 ,  const int& t1 ) { return max( t0 , t1 ); }
inline const int& minus_one() { static const int n = -1; return n; }

template <typename T , int size_max>
class CoordinateCompress
{

private:
  T m_a[size_max];
  map<T,int> m_enum;
  bool m_compressed;
  int m_size;

public:
  inline CoordinateCompress();
  template <typename U , int length_max> inline CoordinateCompress( const U ( &a )[length_max] , const int& length );

  template <typename U , int length_max> inline void Insert( const U ( &a )[length_max] , const int& length );

  inline const T& GetSmallest( const int& i = 0 );
  inline const T& GetLargest( const int& i = 0 );
  inline int GetOrder( const T& t );
  inline const int& size();

private:
  inline void Compress();
  
};

template <typename T , int size_max> inline CoordinateCompress<T,size_max>::CoordinateCompress() : m_a() , m_enum() , m_compressed() , m_size() {}
template <typename T , int size_max> template <typename U , int length_max> inline CoordinateCompress<T,size_max>::CoordinateCompress( const U ( &a )[length_max] , const int& length ) : CoordinateCompress() { Insert( a , length ); }

template <typename T , int size_max> template <typename U , int length_max> inline void CoordinateCompress<T,size_max>::Insert( const U ( &a )[length_max] , const int& length ) { assert( length <= length_max ); if( length > 0 ){ for( int i = 0 ; i < length ; i++ ){ m_enum[ a[i] ]; } assert( ( m_size = m_enum.size() ) <= size_max ); m_compressed = false; } }

template <typename T , int size_max> inline const T& CoordinateCompress<T,size_max>::GetSmallest( const int& i ) { if( ! m_compressed ){ Compress(); } assert( i < m_size ); return m_a[i]; }
template <typename T , int size_max> inline const T& CoordinateCompress<T,size_max>::GetLargest( const int& i ) { if( ! m_compressed ){ Compress(); } assert( i < m_size ); return m_a[m_size - i - 1]; }
template <typename T , int size_max> inline int CoordinateCompress<T,size_max>::GetOrder( const T& t ) { if( ! m_compressed ){ Compress(); } return m_enum.count( t ) == 1 ? m_enum[t] : -1; }
template <typename T , int size_max> inline const int& CoordinateCompress<T,size_max>::size() { return m_size; }

template <typename T , int size_max> inline void CoordinateCompress<T,size_max>::Compress() { m_size = 0; for( auto itr = m_enum.begin() , end = m_enum.end() ; itr != end ; itr++ ){ m_a[m_size] = itr->first; itr->second = m_size++; } m_compressed = true; }

int main()
{
  UNTIE;
  DEXPR( int , bound_N , 100000 , 100 );
  CIN_ASSERT( N , 1 , bound_N );
  CEXPR( int , bound_A , 1000000000 );
  CIN_ASSERT( A , 1 , bound_A );
  int X[bound_N];
  FOR( n , 0 , N ){
    CIN_ASSERT( Xn , 0 , A );
    X[n] = Xn;
  }
  CEXPR( int , bound_T , bound_N );
  CIN_ASSERT( T , 1 , bound_T );
  int L[bound_T];
  int R[bound_T];
  FOR( t , 0 , T ){
    CIN_ASSERT( Lt , 0 , A );
    CIN_ASSERT( Rt , Lt , A );
    L[t] = Lt;
    R[t] = Rt;
  }
  CHECK_REDUNDANT_INPUT;
  CEXPR( int , bound_size , bound_N + bound_T * 2 );
  CoordinateCompress<int,bound_size> cc{};
  cc.Insert( X , N );
  cc.Insert( L , T );
  cc.Insert( R , T );
  FOR( n , 0 , N ){
    int& Xn = X[n];
    Xn = cc.GetOrder( Xn );
  }
  FOR( t , 0 , T ){
    int& Lt = L[t];
    int& Rt = R[t];
    Lt = cc.GetOrder( Lt );
    Rt = cc.GetOrder( Rt );
  }
  const int& size = cc.size();
  int DSD_prep[bound_size] = {};
  FOR( i , 0 , size ){
    DSD_prep[i] = -1;
  }
  DualSqrtDecomposition<int,max_int,minus_one,int,max_int,bound_size> DSD{ DSD_prep };
  FOR( t , 0 , T ){
    DSD.IntervalAct( L[t] , R[t] , t + 1 );
  }
  FOR( n , 0 , N ){
    COUT( DSD.Get( X[n] ) );
  }
  QUIT;
}

yukicoder

結果

テストケース

ソースコード