結果

問題 No.2065 Sum of Min
ユーザー 👑 p-adicp-adic
提出日時 2022-08-30 10:58:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,227 bytes
コンパイル時間 2,708 ms
コンパイル使用メモリ 204,048 KB
実行使用メモリ 19,840 KB
最終ジャッジ日時 2024-11-07 06:11:23
合計ジャッジ時間 6,612 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
18,304 KB
testcase_01 AC 9 ms
12,928 KB
testcase_02 AC 9 ms
13,056 KB
testcase_03 AC 10 ms
12,928 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
権限があれば一括ダウンロードができます

ソースコード

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

#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[A_comp_j]++;				\
      if( A_comp_max_plus <= A_comp_j ){		\
	A_comp_max_plus = A_comp_j + 1;			\
      }							\
    }							\
    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];			\
  ll& min_sum_i = min_sum[ I ];				\
  FOR( j , X_comp_i , A_comp_max_plus ){		\
    min_sum_i += InvA_comp[j];				\
  }							\
  min_sum_i *= AX_sorted_comp[X_comp_i];		\
  FOR( j , 0 , X_comp_i ){				\
    min_sum_i += InvA_comp[j] * AX_sorted_comp[j];	\
  }							\
							\


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_lim];
  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;
  ll InvA_comp[N_lim2] = {};
  ll min_sum[N_lim2] = {};
  int A_comp_max_plus = 0;
  {
    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;
}
0