結果

問題 No.2197 Same Dish
コンテスト
ユーザー 👑 p-adic
提出日時 2022-10-24 12:30:51
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,262 bytes
コンパイル時間 1,710 ms
コンパイル使用メモリ 197,240 KB
最終ジャッジ日時 2025-02-08 12:12:22
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 愚直解（O(N max_i Ri)）チェック
#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:
  int m_Li;
  int m_Ri;
  inline Span( int Li = 0 , int 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; };
};

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 int 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;
  int count[bound_Ri + 1]{};
  int num;
  int max_Ri = 0;
  FOR( i , 0 , N ){
    Span& Si = S[i];
    num = 0;
    FOR( j , Si.m_Li , max_Ri ){
      num += count[j];
    }
    comp = ( comp * ( K - num ) ) % P;
    count[ Si.m_Ri - 1 ]++;
    if( max_Ri < Si.m_Ri ){
      max_Ri = Si.m_Ri;
    }
  }
  RETURN( ( total + P - comp ) % P );
}
0