結果
問題 | No.2716 Falcon Method |
ユーザー | 👑 p-adic |
提出日時 | 2024-02-07 09:13:24 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 137 ms / 2,000 ms |
コード長 | 16,703 bytes |
コンパイル時間 | 3,182 ms |
コンパイル使用メモリ | 223,692 KB |
実行使用メモリ | 16,084 KB |
最終ジャッジ日時 | 2024-09-29 12:55:17 |
合計ジャッジ時間 | 6,260 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,816 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 3 ms
6,820 KB |
testcase_07 | AC | 2 ms
6,820 KB |
testcase_08 | AC | 2 ms
6,816 KB |
testcase_09 | AC | 2 ms
6,816 KB |
testcase_10 | AC | 2 ms
6,816 KB |
testcase_11 | AC | 81 ms
15,364 KB |
testcase_12 | AC | 87 ms
15,408 KB |
testcase_13 | AC | 73 ms
15,696 KB |
testcase_14 | AC | 105 ms
13,436 KB |
testcase_15 | AC | 82 ms
14,976 KB |
testcase_16 | AC | 96 ms
13,504 KB |
testcase_17 | AC | 109 ms
13,852 KB |
testcase_18 | AC | 124 ms
14,396 KB |
testcase_19 | AC | 92 ms
13,260 KB |
testcase_20 | AC | 76 ms
14,908 KB |
testcase_21 | AC | 67 ms
13,812 KB |
testcase_22 | AC | 88 ms
16,084 KB |
testcase_23 | AC | 130 ms
16,064 KB |
testcase_24 | AC | 88 ms
16,000 KB |
testcase_25 | AC | 2 ms
6,820 KB |
testcase_26 | AC | 2 ms
6,820 KB |
testcase_27 | AC | 133 ms
15,996 KB |
testcase_28 | AC | 137 ms
15,964 KB |
ソースコード
// 入力制約チェック #ifndef INCLUDE_MODE #define INCLUDE_MODE // #define REACTIVE // #define USE_GETLINE #endif #ifdef INCLUDE_MAIN inline void Solve() { CEXPR( int , bound_N , 2e5 ); CIN_ASSERT( N , 1 , bound_N ); CEXPR( int , bound_Q , 1e5 ); CIN_ASSERT( Q , 1 , bound_Q ); vector<ll> DR[2]{}; FOR( b , 0 , 2 ){ DR[b].resize( N * 2 ); } int countDR[2]{}; CIN( string , S ); assert( int( S.size() ) == N ); FOR( i , 0 , N ){ assert( S[i] == 'D' || S[i] == 'R' ); int b = S[i] == 'D' ? 0 : 1; DR[b][i] = DR[b][i+N] = 1; ++countDR[b]; } BIT<ll> bitDR[2]{}; FOR( b , 0 , 2 ){ bitDR[b].Set( DR[b] ); } CEXPR( ll , bound_HW , 1e9 ); REPEAT( Q ){ CIN_ASSERT( H , 1 , bound_HW ); CIN_ASSERT( W , 1 , bound_HW ); CIN_ASSERT( P , 0 , N - 1 ); ll HW[2] = { H , W }; ll countHW[2]; FOR( b , 0 , 2 ){ if( countDR[b] > 0 ){ ll q = ( HW[b] - 1 ) / countDR[b]; countHW[b] = q * N; HW[b] -= q * countDR[b]; int i = bitDR[b].BinarySearch( P , HW[b] ); countHW[b] += 1 + i; } else { countHW[b] = 1e15; } } COUT( min( countHW[0] , countHW[1] ) % N ); } } REPEAT_MAIN(1); #else // INCLUDE_MAIN #ifdef INCLUDE_LIBRARY // https://github.com/p-adic/cpp // VVV ライブラリは以下に挿入する。 // 使用演算: // U& U::operator=( const U& ) // U& U::operator+=( const U& ) // U operator-( const U& , const U& )(ただしIntervalSumを用いない場合は不要) // U operator<( const U& , const U& )(ただしBinarySearchを用いない場合は不要) // U()による初期化O(size) // 配列による初期化O(size) // 一点更新O(log_2 size) // +による一点更新O(log_2 size) // 配列の加算による全体更新O(size) // 一点取得O(log_2 size) // LSB切片和取得O(1) // 始切片和取得O(log_2 size) // 区間和取得O(log_2 size) // 始切片和がn以上となる要素の添字の最小値の二分探索O(log_2 size) template <typename U> class BIT { private: int m_size; vector<U> m_fenwick; // m_size以上である最小の2羃。 int m_power; public: inline BIT( const int& size = 0 ); BIT( const vector<U>& a ); inline void Set( const int& i , const U& u ); inline void Set( const vector<U>& a ); inline void Initialise( const int& size = 0 ); inline BIT<U>& operator+=( const vector<U>& a ); void Add( const int& i , const U& u ); inline const int& size() const noexcept; // const参照でないことに注意。 inline U operator[]( const int& i ) const; inline U Get( const int& i ) const; // a[j-(j&-j)]+...+a[j-1]を返す。 inline const U& LSBSegmentSum( const int& j ) const; // a[0]+...+a[i_final]を返す。 U InitialSegmentSum( const int& i_final ) const; // a[i_start]+...+a[i_final]を返す。 inline U IntervalSum( const int& i_start , const int& i_final ) const; // operator+=の単位元U()より小さくない要素のみを成分に持つ場合のみサポート。 // InitialSegmentSum( i )がu以上となるiが存在する場合にその最小値を2進法で探索。 // 存在しない場合はNを返す。 int BinarySearch( const U& u ) const; // IntervalSum( i_start , i )がu以上となるi_start以上のiが存在する場合にその最小値を2進法で探索。 // 存在しない場合はNを返す。 inline int BinarySearch( const int& i_start , const U& u ) const; }; template <typename U> inline BIT<U>::BIT( const int& size ) : m_size( size ) , m_fenwick( m_size + 1 ) , m_power( 1 ) { static_assert( ! is_same<U,int>::value ); while( m_power < m_size ){ m_power <<= 1; } } template <typename U> BIT<U>::BIT( const vector<U>& a ) : BIT( a.size() ) { for( int j = 1 ; j <= m_size ; j++ ){ U& fenwick_j = m_fenwick[j]; int i = j - 1; fenwick_j = a[i]; int i_lim = j - ( j & -j ); while( i > i_lim ){ fenwick_j += m_fenwick[i]; i -= ( i & -i ); } } } template <typename U> inline void BIT<U>::Set( const int& i , const U& u ) { Add( i , u - IntervalSum( i , i ) ); } template <typename U> inline void BIT<U>::Set( const vector<U>& a ) { *this = BIT<U>{ a }; } template <typename U> inline void BIT<U>::Initialise( const int& size ) { *this = BIT<U>( size ); } template <typename U> inline BIT<U>& BIT<U>::operator+=( const vector<U>& a ) { BIT<U> a_copy{ a }; assert( m_size == a.m_size ); for( int j = 1 ; j <= m_size ; j++ ){ m_fenwick[j] += a.m_fenwick[j]; } return *this; } template <typename U> void BIT<U>::Add( const int& i , const U& u ) { assert( 0 <= i && i < m_size ); int j = i + 1; while( j <= m_size ){ m_fenwick[j] += u; j += ( j & -j ); } return; } template <typename U> inline const int& BIT<U>::size() const noexcept { return m_size; } template <typename U> inline U BIT<U>::operator[]( const int& i ) const { assert( 0 <= i && i < m_size ); return IntervalSum( i , i ); } template <typename U> inline U BIT<U>::Get( const int& i ) const { return operator[]( i ); } template <typename U> inline const U& BIT<U>::LSBSegmentSum( const int& j ) const { assert( 0 < j && j <= m_size ); return m_fenwick[j]; } template <typename U> U BIT<U>::InitialSegmentSum( const int& i_final ) const { U sum = 0; int j = ( i_final < m_size ? i_final : m_size - 1 ) + 1; while( j > 0 ){ sum += m_fenwick[j]; j -= j & -j; } return sum; } template <typename U> inline U BIT<U>::IntervalSum( const int& i_start , const int& i_final ) const { return InitialSegmentSum( i_final ) - InitialSegmentSum( i_start - 1 ); } template <typename U> int BIT<U>::BinarySearch( const U& u ) const { int power = m_power; int j = 0; U sum{}; U sum_next{}; while( power > 0 ){ int j_next = j | power; if( j_next <= m_size ){ sum_next += m_fenwick[j_next]; if( sum_next < u ){ sum = sum_next; j = j_next; } else { sum_next = sum; } } power >>= 1; } // InitialSegmentSum( i )がu未満となるiが存在するならばjはその最大値に1を足したものとなり、 // InitialSegmentSum( i )がu未満となるiが存在しないならばj=0となり、 // いずれの場合もInitialSegmentSum( i )がu以上となるiが存在するならば // jはそのような最小のiと等しい。 return j; } template <typename U> inline int BIT<U>::BinarySearch( const int& i_start , const U& u ) const { return max( i_start , BinarySearch( InitialSegmentSum( i_start - 1 ) + u ) ); } // AAA ライブラリは以上に挿入する。 #define INCLUDE_MAIN #include __FILE__ #else // INCLUDE_LIBRARY #ifdef DEBUG #define _GLIBCXX_DEBUG #define SIGNAL signal( SIGABRT , &AlertAbort ); #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE ) #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック: " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) ) #define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl #define COUT( ... ) VariadicCout( cout << "出力: " , __VA_ARGS__ ) << endl #define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl #define COUT_A( A , N ) cout << "出力: "; OUTPUT_ARRAY( cout , A , N ) << endl #define CERR_ITR( A ) OUTPUT_ITR( cerr , A ) << endl #define COUT_ITR( A ) cout << "出力: "; OUTPUT_ITR( cout , A ) << endl #else #pragma GCC optimize ( "O3" ) #pragma GCC optimize ( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #define SIGNAL #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE ) #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #define CERR( ... ) #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL #define CERR_A( A , N ) #define COUT_A( A , N ) OUTPUT_ARRAY( cout , A , N ) << ENDL #define CERR_ITR( A ) #define COUT_ITR( A ) OUTPUT_ITR( cout , A ) << ENDL #endif #ifdef REACTIVE #define ENDL endl #else #define ENDL "\n" #endif #ifdef USE_GETLINE #define SET_LL( A ) { GETLINE( A ## _str ); A = stoll( A ## _str ); } #define GETLINE_SEPARATE( SEPARATOR , ... ) string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ ) #define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ ) #else #define SET_LL( A ) cin >> A #define CIN( LL , ... ) LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ ) #define SET_A( A , N ) FOR( VARIABLE_FOR_CIN_A , 0 , N ){ cin >> A[VARIABLE_FOR_CIN_A]; } #define CIN_A( LL , A , N ) vector<LL> A( N ); SET_A( A , N ); #endif #include <bits/stdc++.h> using namespace std; #define REPEAT_MAIN( BOUND ) int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); SIGNAL; DEXPR( int , bound_test_case_num , BOUND , min( BOUND , 100 ) ); int test_case_num = 1; if constexpr( bound_test_case_num > 1 ){ SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } REPEAT( test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); } Solve(); CERR( "" ); } CHECK_REDUNDANT_INPUT; } #define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now() #define CURRENT_TIME static_cast<double>( chrono::duration_cast<chrono::microseconds>( chrono::system_clock::now() - watch ).count() / 1000.0 ) #define CHECK_WATCH( TL_MS ) ( CURRENT_TIME < TL_MS - 100.0 ) #define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE #define SET_ASSERT( A , MIN , MAX ) SET_LL( A ); ASSERT( A , MIN , MAX ) #define CIN_ASSERT( A , MIN , MAX ) decldecay_t( MAX ) A; SET_ASSERT( A , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( decldecay_t( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( decldecay_t( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define FOREQINV( VAR , INITIAL , FINAL ) for( decldecay_t( INITIAL ) VAR = INITIAL ; VAR + 1 > 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 SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS ) #define OUTPUT_ARRAY( OS , A , N ) FOR( VARIABLE_FOR_OUTPUT_ARRAY , 0 , N ){ OS << A[VARIABLE_FOR_OUTPUT_ARRAY] << (VARIABLE_FOR_OUTPUT_ARRAY==N-1?"":" "); } OS #define OUTPUT_ITR( OS , A ) { auto ITERATOR_FOR_OUTPUT_ITR = A.begin() , END_FOR_OUTPUT_ITR = A.end(); bool VARIABLE_FOR_OUTPUT_ITR = ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR; while( VARIABLE_FOR_OUTPUT_ITR ){ OS << *ITERATOR_FOR_COUT_ITR; ( VARIABLE_FOR_OUTPUT_ITR = ++ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR ) ? OS : OS << " "; } } OS #define RETURN( ... ) COUT( __VA_ARGS__ ); return // 型のエイリアス #define decldecay_t( VAR ) decay_t<decltype( VAR )> template <typename F , typename...Args> using ret_t = decltype( declval<F>()( declval<Args>()... ) ); template <typename T> using inner_t = typename T::type; using uint = unsigned int; using ll = long long; using ull = unsigned long long; using ld = long double; using lld = __float128; template <typename INT> using T2 = pair<INT,INT>; template <typename INT> using T3 = tuple<INT,INT,INT>; template <typename INT> using T4 = tuple<INT,INT,INT,INT>; // 入出力用 template <class Traits> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is ) { return is; } template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is , Arg& arg , ARGS&... args ) { return VariadicCin( is >> arg , args... ); } template <class Traits> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator ) { return is; } template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator , Arg& arg , ARGS&... args ) { return VariadicGetline( getline( is , arg , separator ) , separator , args... ); } template <class Traits , typename Arg> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const vector<Arg>& arg ) { auto begin = arg.begin() , end = arg.end(); auto itr = begin; while( itr != end ){ ( itr == begin ? os : os << " " ) << *itr; itr++; } return os; } template <class Traits , typename Arg> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg& arg ) { return os << arg; } template <class Traits , typename Arg1 , typename Arg2 , typename... ARGS> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg1& arg1 , const Arg2& arg2 , const ARGS&... args ) { return VariadicCout( os << arg1 << " " , arg2 , args... ); } // デバッグ用 #ifdef DEBUG inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); } void AutoCheck( bool& auto_checked ); #endif // 入力フォーマットチェック用 // 1行中の変数の個数をSEPARATOR区切りで確認 #define GETLINE_COUNT( S , VARIABLE_NUMBER , SEPARATOR ) 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 ) == SEPARATOR ){ count++; } } assert( count + 1 == VARIABLE_NUMBER ); } // 余計な入力の有無を確認 #ifdef DEBUG #define CHECK_REDUNDANT_INPUT #else #ifdef USE_GETLINE #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 ) #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 ) #endif #endif // |N| <= BOUNDを満たすNをSから構築 #define STOI( S , N , BOUND ) decldecay_t( 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 ++; } } #define INCLUDE_LIBRARY #include __FILE__ #endif // INCLUDE_LIBRARY #endif // INCLUDE_MAIN