結果

問題 No.2080 Simple Nim Query
ユーザー 👑 p-adicp-adic
提出日時 2022-09-25 23:38:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 124 ms / 3,000 ms
コード長 3,859 bytes
コンパイル時間 1,680 ms
コンパイル使用メモリ 200,000 KB
実行使用メモリ 6,804 KB
最終ジャッジ日時 2023-09-03 02:50:04
合計ジャッジ時間 3,360 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,556 KB
testcase_01 AC 3 ms
6,512 KB
testcase_02 AC 3 ms
6,564 KB
testcase_03 AC 46 ms
6,804 KB
testcase_04 AC 45 ms
6,568 KB
testcase_05 AC 83 ms
6,576 KB
testcase_06 AC 117 ms
6,568 KB
testcase_07 AC 124 ms
6,504 KB
testcase_08 AC 84 ms
6,504 KB
testcase_09 AC 78 ms
6,628 KB
testcase_10 AC 68 ms
6,488 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0