結果

問題 No.2650 [Cherry 6th Tune *] セイジャク
コンテスト
ユーザー 👑 p-adic
提出日時 2023-07-25 16:52:12
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 412 ms / 2,500 ms
コード長 11,856 bytes
コンパイル時間 3,657 ms
コンパイル使用メモリ 111,952 KB
最終ジャッジ日時 2025-02-15 19:00:56
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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 );
  CEXPR( int , bound_T , bound_N );
  CEXPR( int , bound_size , bound_N + bound_T * 2 );
  map<int,int> TheAt{};
  int X[bound_N];
  FOR( n , 0 , N ){
    CIN_ASSERT( Xn , 0 , A );
    TheAt[ X[n] = Xn ];
  }
  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 );
    TheAt[ L[t] = Lt ];
    TheAt[ R[t] = Rt ];
  }
  CHECK_REDUNDANT_INPUT;
  int size = 0;
  FOR_ITR( TheAt ){
    itr->second = size++;
  }
  FOR( n , 0 , N ){
    int& Xn = X[n];
    Xn = TheAt[Xn];
  }
  FOR( t , 0 , T ){
    int& Lt = L[t];
    int& Rt = R[t];
    Lt = TheAt[Lt];
    Rt = TheAt[Rt];
  }
  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;
}
0