#810522 (C++17) No.2197 Same Dish

提出ソース

結果

問題	No.2197 Same Dish
ユーザー	👑 p-adic
提出日時	2022-10-24 11:51:00
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	43 ms / 2,000 ms
コード長	5,623 bytes
コンパイル時間	2,051 ms
コンパイル使用メモリ	202,760 KB
実行使用メモリ	8,360 KB
最終ジャッジ日時	2023-09-05 13:05:48
合計ジャッジ時間	3,504 ms
ジャッジサーバーID （参考情報）	judge14 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 8,096 KB
testcase_01	AC	4 ms 8,092 KB
testcase_02	AC	4 ms 8,092 KB
testcase_03	AC	4 ms 8,360 KB
testcase_04	AC	4 ms 8,084 KB
testcase_05	AC	3 ms 8,040 KB
testcase_06	AC	4 ms 8,076 KB
testcase_07	AC	4 ms 8,136 KB
testcase_08	AC	4 ms 8,108 KB
testcase_09	AC	4 ms 8,040 KB
testcase_10	AC	4 ms 8,052 KB
testcase_11	AC	4 ms 8,240 KB
testcase_12	AC	4 ms 8,068 KB
testcase_13	AC	9 ms 8,212 KB
testcase_14	AC	39 ms 8,104 KB
testcase_15	AC	43 ms 8,360 KB
testcase_16	AC	30 ms 8,160 KB
testcase_17	AC	26 ms 8,056 KB
testcase_18	AC	43 ms 8,096 KB
testcase_19	AC	43 ms 8,064 KB
testcase_20	AC	43 ms 8,064 KB
testcase_21	AC	41 ms 8,156 KB
testcase_22	AC	38 ms 8,096 KB

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

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;

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 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 QUIT return 0 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT 

#define POWER( ANSWER , VAR , EXPONENT_REF , MODULO )			\
  TYPE_OF( VAR ) ANSWER = 1;						\
  TYPE_OF( VAR ) VARIABLE_FOR_SQUARE_FOR_POWER = VAR;			\
  while( EXPONENT_REF != 0 ){						\
    if( EXPONENT_REF % 2 == 1 ){					\
      ANSWER = ( ANSWER * VARIABLE_FOR_SQUARE_FOR_POWER ) % MODULO;	\
    }									\
    VARIABLE_FOR_SQUARE_FOR_POWER = ( VARIABLE_FOR_SQUARE_FOR_POWER * VARIABLE_FOR_SQUARE_FOR_POWER ) % MODULO;	\
    EXPONENT_REF /= 2;							\
  }									\


class Span
{
public:
  ll m_Li;
  ll m_Ri;
  inline Span( const ll& Li = 0 , const ll& Ri = 0 ) : m_Li( Li ) , m_Ri( Ri ) {}
};

class Ord
{
public:
  inline Ord() = default;
  inline bool operator()( const Span& S0 , const Span& S1 ) { return S0.m_Li < S1.m_Li; };
};

//  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 + 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:
  BIT<T,N> m_bit_0;
  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 , - n * ( i_start - 1 ) ); m_bit_0.Add( i_final + 1 , n * i_final ); 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;
  constexpr const int bound_N = 100000;
  CIN_ASSERT( N , 1 , bound_N );
  constexpr const ll bound_K = 1000000000;
  CIN_ASSERT( K , 1 , bound_K );
  constexpr const ll bound_Ri = 200000;
  Span S[bound_N] = {};
  FOR( i , 0 , N ){
    Span& Si = S[i];
    cin >> Si.m_Li >> Si.m_Ri;
    assert( 1 <= Si.m_Li && Si.m_Li < Si.m_Ri && Si.m_Ri <= bound_Ri );
  }
  constexpr const ll P = 998244353;
  int N_copy = N;
  POWER( total , K , N_copy , P );
  sort( S , S + N , Ord() );
  ll comp = 1;
  IntervalAddBIT<ll,bound_Ri + 1> mult{};
  FOR( i , 0 , N ){
    Span& Si = S[i];
    comp = ( comp * ( K - mult.IntervalSum( Si.m_Li , Si.m_Li ) ) ) % P;
    mult.IntervalAdd( Si.m_Li , Si.m_Ri - 1 , 1 );
  }
  RETURN( ( total + P - comp ) % P );
}

yukicoder

結果

テストケース

ソースコード