結果

問題 No.2452 Incline
ユーザー 👑 p-adicp-adic
提出日時 2023-08-19 13:44:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 380 ms / 2,000 ms
コード長 7,118 bytes
コンパイル時間 3,591 ms
コンパイル使用メモリ 227,860 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-09 08:38:17
合計ジャッジ時間 7,212 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 380 ms
5,376 KB
testcase_04 AC 277 ms
5,376 KB
testcase_05 AC 231 ms
5,376 KB
testcase_06 AC 271 ms
5,376 KB
testcase_07 AC 247 ms
5,376 KB
testcase_08 AC 142 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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( MESSAGE ) cerr << MESSAGE << 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 ) )
#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( MESSAGE ) 
  #define COUT( ANSWER ) cout << ANSWER << "\n"
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#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 SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_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 REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define QUIT return 0

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

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

int main()
{
  UNTIE;
  
  DEXPR( int , bound_T , 100000 , 100 ); // 0が5個
  GETLINE_COUNT( T_str , 1 );
  STOI( T_str , T , bound_T );
  CEXPR( ll , bound_NM , 1000000000000000000 ); // 0が18個
  CEXPR( ll , P , 998244353 );
  CEXPR( ll , two_inv , ( P + 1 ) / 2 );
  REPEAT( T ){
    GETLINE_COUNT( NMLR_str , 4 );
    STOI( NMLR_str , N , bound_NM );
    STOI( NMLR_str , M , bound_NM );
    STOI( NMLR_str , L , M );
    STOI( NMLR_str , R , M );
    N--;
    ll d_max = R / N;
    ll d_min = -( ( M - L ) / N );
    ll d_0 = - ( ( M - R ) / N );
    ll d_1 = L / N;

    // sum( ll d = d_min ; d <= d_max ; d++ ){ min( R - d * N , M ) - max( L - d * N , 0 ) + 1 };

    // = sum( ll d = d_min ; d <= d_max ; d++ ){ min( R - d * N , M ) }
    //   - sum( ll d = d_min ; d <= d_max ; d++ ){ max( L - d * N , 0 ) }
    //   + d_max - d_min + 1;

    // = sum( ll d = d_min ; d < d_0 ; d++ ){ M }
    //   + sum( ll d = d_0 ; d <= d_max ; d++ ){ R - d * N }
    //   - sum( ll d = d_min ; d <= d_1 ; d++ ){ L - d * N }
    //   - sum( ll d = d_1 + 1 ; d <= d_max ; d++ ){ 0 }
    //   + d_max - d_min + 1;

    // = M * ( d_0 - d_min )
    //   + R * ( d_max - d_0 + 1 ) - ( ( d_max + d_0 ) * ( d_max - d_0 + 1 ) / 2 ) * N
    //   - L * ( d_1 - d_min + 1 ) + ( ( d_1 + d_min ) * ( d_1 - d_min + 1 ) / 2 ) * N
    //   - 0
    //   + d_max - d_min + 1;

    N %= P;
    M %= P;
    L %= P;
    R %= P;
    d_max %= P;
    d_min %= P;
    d_0 %= P;
    d_1 %= P;
    COUT( Residue( M * ( d_0 - d_min ) % P + R * ( d_max - d_0 + 1 ) % P + ( ( d_1 + d_min ) * ( d_1 - d_min + 1 ) - ( d_max + d_0 ) * ( d_max - d_0 + 1 ) ) % P * two_inv % P * N % P - L * ( d_1 - d_min + 1 ) % P + d_max - d_min + 1 , P ) );
  }
  CHECK_REDUNDANT_INPUT;
  cerr << "テストケースの強さ確認： T = " << T << "\n";
  QUIT;
}
0