#794123 (C++17) No.2065 Sum of Min

提出ソース

結果

問題	No.2065 Sum of Min
ユーザー	👑 p-adic
提出日時	2022-08-30 18:41:07
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	134 ms / 2,000 ms
コード長	5,036 bytes
コンパイル時間	2,401 ms
コンパイル使用メモリ	204,680 KB
実行使用メモリ	20,736 KB
最終ジャッジ日時	2024-11-07 12:52:58
合計ジャッジ時間	7,696 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	12 ms 17,536 KB
testcase_01	AC	12 ms 17,536 KB
testcase_02	AC	13 ms 17,536 KB
testcase_03	AC	13 ms 17,408 KB
testcase_04	AC	97 ms 19,840 KB
testcase_05	AC	84 ms 19,968 KB
testcase_06	AC	83 ms 18,944 KB
testcase_07	AC	77 ms 19,072 KB
testcase_08	AC	97 ms 18,944 KB
testcase_09	AC	127 ms 20,608 KB
testcase_10	AC	104 ms 20,608 KB
testcase_11	AC	102 ms 20,608 KB
testcase_12	AC	128 ms 20,608 KB
testcase_13	AC	129 ms 20,736 KB
testcase_14	AC	127 ms 20,608 KB
testcase_15	AC	130 ms 20,736 KB
testcase_16	AC	132 ms 20,608 KB
testcase_17	AC	129 ms 20,608 KB
testcase_18	AC	131 ms 20,736 KB
testcase_19	AC	130 ms 20,608 KB
testcase_20	AC	133 ms 20,736 KB
testcase_21	AC	134 ms 20,608 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

#define CIN( LL , A ) LL A; cin >> A 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( int VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; return 0 

class Pair
{
public:
  ll m_a;
  int m_i;
  inline Pair( const ll& a = 0 , const int& i = 0 ) : m_a( a ) , m_i( i ) {}
};

class Order_a
{
public:
  inline bool operator()( const Pair& p0 , const Pair& p1 ) { return p0.m_a < p1.m_a; };
};


// 以下自分のライブラリ（https://github.com/p-adic/cpp）よりソースコードをコピーして編集している。

//  InitialSegmentSumで負の入力を扱うために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 ); }


#define SET_MIN_SUM( I , PREV )						\
  Pair& LR_sorted_i = LR_sorted[ I ];					\
  if( LR_sorted_prev != LR_sorted_i.m_a ){				\
    LR_sorted_comp_length_minus++;					\
    FOR( j , PREV , LR_sorted_i.m_a ){					\
      int& A_comp_j = A_comp[j];					\
      InvA_comp.Add( A_comp_j , 1 );					\
      InvA_comp_A.Add( A_comp_j , AX_sorted_comp[A_comp_j] );		\
      if( A_comp_max < A_comp_j ){					\
	A_comp_max = A_comp_j;						\
      }									\
    }									\
    LR_sorted_prev = LR_sorted_i.m_a;					\
  }									\
  i_half = LR_sorted_i.m_i / 2;						\
  if( LR_sorted_i.m_i % 2 == 0 ){					\
    L_num[i_half] = I;							\
  } else {								\
    R_num[i_half] = I;							\
  }									\
  int& X_comp_i = X_comp[i_half];					\
  min_sum[ I ] += InvA_comp_A.InitialSegmentSum( X_comp_i ) + InvA_comp.IntervalSum( X_comp_i + 1 , A_comp_max ) * AX_sorted_comp[X_comp_i]; \
									\


int main(){
  ios_base::sync_with_stdio( false );
  cin.tie( nullptr );
  constexpr const int N_lim = 100002;
  constexpr const int N_lim2 = N_lim * 2;
  CIN( int , N );
  CIN( int , Q );
  Pair AX[N_lim2];
  FOR( i , 0 , N ){
    Pair& Ai = AX[i];
    cin >> Ai.m_a;
    Ai.m_i = i;
  }
  Pair LR[N_lim2];
  int i2;
  int i2_plus;
  int Ni;
  FOR( i , 0 , Q ){
    i2 = i * 2;
    i2_plus = i2 + 1;
    Pair& Li = LR[i2];
    Pair& Ri = LR[i2_plus];
    cin >> Li.m_a;
    Li.m_a--;
    Li.m_i = i2;
    cin >> Ri.m_a;
    Ri.m_i = i2_plus;
    Ni = N + i;
    Pair& Xi = AX[Ni];
    cin >> Xi.m_a;
    Xi.m_i = Ni;
  }
  Order_a ord{};
  ll NQ = N + Q;
  sort( AX , AX + NQ , ord );
  Pair ( &AX_sorted )[N_lim2] = AX;
  int A_comp[N_lim];
  int X_comp[N_lim];
  ll AX_sorted_comp[N_lim2];
  ll AX_sorted_comp_prev = -1;
  int AX_sorted_comp_length_minus = -1;
  FOR( i , 0 , NQ ){
    Pair& AX_sorted_i = AX_sorted[i];
    if( AX_sorted_comp_prev != AX_sorted_i.m_a ){
      AX_sorted_comp_length_minus++;
      AX_sorted_comp[AX_sorted_comp_length_minus] = AX_sorted_i.m_a;
      AX_sorted_comp_prev = AX_sorted_i.m_a;
    }
    if( AX_sorted_i.m_i < N ){
      A_comp[AX_sorted_i.m_i] = AX_sorted_comp_length_minus;
    } else {
      X_comp[AX_sorted_i.m_i - N] = AX_sorted_comp_length_minus;
    }
  }
  ll Q2 = Q * 2;
  sort( LR , LR + Q2 , ord );
  Pair ( &LR_sorted )[N_lim2] = LR;
  int L_num[N_lim];
  int R_num[N_lim];
  int LR_sorted_prev = -1;
  int LR_sorted_comp_length_minus = -1;
  int i_half;
  HybridBIT<ll,N_lim2> InvA_comp{};
  HybridBIT<ll,N_lim2> InvA_comp_A{};
  ll min_sum[N_lim2] = {};
  int A_comp_max = -1;
  {
    SET_MIN_SUM( 0 , 0 );
  }
  FOR( i , 1 , Q2 ){
    SET_MIN_SUM( i , LR_sorted_prev );
  }
  FOR( i , 0 , Q ){
    cout << min_sum[R_num[i]] - min_sum[L_num[i]] << "\n";
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード