結果
問題 | No.2080 Simple Nim Query |
ユーザー | 👑 p-adic |
提出日時 | 2022-09-25 23:38:41 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 137 ms / 3,000 ms |
コード長 | 3,859 bytes |
コンパイル時間 | 2,261 ms |
コンパイル使用メモリ | 201,500 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 07:26:00 |
合計ジャッジ時間 | 4,016 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,812 KB |
testcase_01 | AC | 3 ms
6,940 KB |
testcase_02 | AC | 4 ms
6,940 KB |
testcase_03 | AC | 48 ms
6,940 KB |
testcase_04 | AC | 50 ms
6,940 KB |
testcase_05 | AC | 92 ms
6,940 KB |
testcase_06 | AC | 137 ms
6,940 KB |
testcase_07 | AC | 132 ms
6,944 KB |
testcase_08 | AC | 94 ms
6,944 KB |
testcase_09 | AC | 95 ms
6,940 KB |
testcase_10 | AC | 76 ms
6,944 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using uint = unsigned int; using ll = long long; #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CIN( LL , A ) LL A; cin >> A #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( remove_const<remove_reference<decltype( FINAL_PLUS_ONE )>::type >::type VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( remove_const<remove_reference<decltype( FINAL )>::type >::type VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) #define QUIT return 0 #define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT #define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << "\n"; QUIT #define MIN( A , B ) ( A < B ? A : B ) #define MAX( A , B ) ( A < B ? B : A ) template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : - a; } // InitialSegmentSumで負の入力を扱うためにuintではなくintをテンプレート引数にする。 template <typename T , int N> class HybridBIT { private: T m_a[N]; T m_fenwick[N + 1]; public: inline HybridBIT(); inline HybridBIT( const T ( & a )[N] ); inline const T& operator[]( const int& i ) const; inline HybridBIT<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 HybridBIT<T,N>::HybridBIT() : m_a() , m_fenwick() {} template <typename T , int N> inline HybridBIT<T,N>::HybridBIT( const T ( & a )[N] ) : m_a() , m_fenwick() { operator+=( a ); } template <typename T , int N> inline const T& HybridBIT<T,N>::operator[]( const int& i ) const { return m_a[i]; } template <typename T , int N> inline HybridBIT<T,N>& HybridBIT<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 HybridBIT<T,N>::Add( const int& i , const T& n ) { m_a[i] += n; int j = i + 1; while( j <= N ){ m_fenwick[j] += n; j += ( j & -j ); } return; } template <typename T , int N> T HybridBIT<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 HybridBIT<T,N>::IntervalSum( const int& i_start , const int& i_final ) { return InitialSegmentSum( i_final ) - InitialSegmentSum( i_start - 1 ); } int main() { UNTIE; CIN( ll , N ); ll power_max = 1; power_max <<= 20; while( N <= power_max ){ power_max /= 2; } CIN( ll , Q ); HybridBIT<ll,200000> A{}; ll Ai; FOR( i , 0 , N ){ cin >> Ai; A.Add( i , 2 - MIN( Ai , 2 ) ); } ll T , X , Y , sum , count , count_new , L , power; REPEAT( Q ){ cin >> T >> X >> Y; --X; if( T == 1 ){ A.Add( X , ( 2 - MIN( Y , 2 ) ) - A[X] ); } else { --Y; if( A[Y] == 0 ){ cout << "F" << "\n"; } else { L = Y - X + 1; power = power_max; while( L < power ){ power /= 2; } sum = A.InitialSegmentSum( Y ); count = 0; while( power != 0 ){ count_new = count + power; if( L >= count_new ){ if( sum - A.InitialSegmentSum( Y - count_new ) == count_new ){ count = count_new; } } power /= 2; } if( L == count ){ count--; } cout << ( count % 2 == 0 ? "F" : "S" ) << "\n"; } } } QUIT; }