結果

問題 No.2065 Sum of Min
ユーザー 👑 p-adic
提出日時 2022-08-30 18:41:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 128 ms / 2,000 ms
コード長 5,036 bytes
コンパイル時間 1,908 ms
コンパイル使用メモリ 197,028 KB
最終ジャッジ日時 2025-02-06 23:59:51
ジャッジサーバーID
(参考情報)
judge1 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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
// InitialSegmentSumint
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0