結果

問題 No.2065 Sum of Min
ユーザー 👑 p-adicp-adic
提出日時 2022-08-29 16:49:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 5,050 bytes
コンパイル時間 2,351 ms
コンパイル使用メモリ 203,040 KB
実行使用メモリ 482,176 KB
最終ジャッジ日時 2024-11-06 19:18:43
合計ジャッジ時間 8,564 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 324 ms
481,536 KB
testcase_01 AC 319 ms
476,288 KB
testcase_02 AC 321 ms
476,416 KB
testcase_03 AC 325 ms
476,288 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_LL( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR_LL( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; return 0 
#define MIN( A , B ) A < B ? A : B 

#define SET_BC					\
  ll& Ai = A[i];				\
  if( Ai <= thr ){				\
    num = i / N_lim_D_sum_d;			\
    B_val_d[B_length_d] = Ai;			\
    B_val_sum_d_num += Ai;			\
    B_ind_d[B_length_d] = i;			\
    B_ind_count_d_num++;			\
    B_length_d++;				\
  } else if( Ai < thr_plus ){			\
    C_val_d[C_length_d] = Ai;			\
    C_ind_d[C_length_d] = i;			\
    C_length_d++;				\
  }						\
						\


int main(){
  ios_base::sync_with_stdio( false );
  cin.tie( nullptr );
  constexpr const ll N_lim = 100001;
  CIN( ll , N );
  CIN( ll , Q );
  ll A[N_lim];
  N++;
  FOR_LL( i , 1 , N ){
    cin >> A[i];
  }
  // D_val は ll[D_val_plus][N_lim] が メモリオーバーしない程度に大きい値
  constexpr const ll D_val = 150;
  constexpr const ll D_val_plus = D_val + 1;
  // D_sum は sqrt( N_lim * 2 ) 付近
  constexpr const ll D_sum = 447;
  constexpr const ll D_sum_plus = D_sum + 1;
  ll B_val[D_val_plus][N_lim] = {};
  ll B_val_sum[D_val_plus][D_sum_plus] = {};
  ll B_ind[D_val_plus][N_lim] = {};
  ll B_ind_count[D_val_plus][D_sum_plus] = {};
  ll B_length[D_val_plus] = {};
  ll C_val[D_val_plus][N_lim] = {};
  ll C_ind[D_val_plus][N_lim] = {};
  ll C_length[D_val_plus] = {};
  ll N_lim_D_sum[D_val_plus];
  ll thr;
  ll thr_plus;
  ll num;
  ll i_start;
  ll i_lim;
  constexpr const ll A_div = 1000000001 / D_val;
  FOR_LL( d , 0 , D_val_plus ){
    thr = A_div * d;
    thr_plus = thr + A_div;
    ll ( &B_val_d )[N_lim] = B_val[d];
    ll ( &B_val_sum_d )[D_sum_plus] = B_val_sum[d];
    ll ( &B_ind_d )[N_lim] = B_ind[d];
    ll ( &B_ind_count_d )[D_sum_plus] = B_ind_count[d];
    ll& B_length_d = B_length[d];
    ll ( &C_val_d )[N_lim] = C_val[d];
    ll ( &C_ind_d )[N_lim] = C_ind[d];
    ll& C_length_d = C_length[d];
    ll& N_lim_D_sum_d = N_lim_D_sum[d];
    N_lim_D_sum_d = N / D_sum_plus + ( N % D_sum_plus == 0 ? 0 : 1 );
    {
      i_start = 1;
      i_lim = N_lim_D_sum_d;
      ll& B_val_sum_d_num = B_val_sum_d[0];
      ll& B_ind_count_d_num = B_ind_count_d[0];
      FOR_LL( i , i_start , i_lim ){
	SET_BC;
      }
    }
    FOR_LL( num , 1 , D_sum ){
      i_start = i_lim;
      i_lim += N_lim_D_sum_d;
      ll& B_val_sum_d_num = B_val_sum_d[num];
      ll& B_ind_count_d_num = B_ind_count_d[num];
      FOR_LL( i , i_lim - N_lim_D_sum_d , i_lim ){
	SET_BC;
      }
    }
    {
      ll& B_val_sum_d_num = B_val_sum_d[D_sum];
      ll& B_ind_count_d_num = B_ind_count_d[D_sum];
      FOR_LL( i , i_lim , N ){
	SET_BC;
      }
    }
  }
  ll L;
  ll R;
  ll X;
  ll sum;
  ll count;
  ll d;
  ll num0;
  ll num1;
  ll j_start;
  ll J;
  ll L_plus;
  ll R_minus;
  REPEAT( Q ){
    cin >> L;
    cin >> R;
    cin >> X;
    sum = 0;
    count = 0;
    d = X / A_div;
    ll& N_lim_D_sum_d = N_lim_D_sum[d];
    num0 = L / N_lim_D_sum_d + ( L % N_lim_D_sum_d == 0 ? 0 : 1 );
    num1 = R / N_lim_D_sum_d;
    ll ( &B_val_d )[N_lim] = B_val[d];
    ll ( &B_ind_d )[N_lim] = B_ind[d];
    ll& B_length_d = B_length[d];
    j_start = -1;
    J = B_length_d / 2;
    while( J != 0 ){
      while( j_start + J < B_length_d ? B_ind_d[j_start + J] < L : false ){
	j_start += J;
      }
      J /= 2;
    }
    j_start++;
    if( num0 < num1 ){
      ll ( &B_val_sum_d )[D_sum_plus] = B_val_sum[d];
      ll ( &B_ind_count_d )[D_sum_plus] = B_ind_count[d];
      L_plus = num0 * N_lim_D_sum_d;
      R_minus = num1 * N_lim_D_sum_d;
      FOR_LL( j , j_start , B_length_d ){
	if( B_ind_d[j] < L_plus ){
	  sum += B_val_d[j];
	  count++;
	} else {
	  j_start = j - 1;
	  j = B_length_d;
	}
      }
      FOR_LL( num , num0 , num1 ){
	sum += B_val_sum_d[num];
	count += B_ind_count_d[num];
      }
      J = B_length_d / 2;
      while( J != 0 ){
	while( j_start + J < B_length_d ? B_ind_d[j_start + J] < R_minus : false ){
	  j_start += J;
	}
	J /= 2;
      }
      j_start++;
      FOR_LL( j , j_start , B_length_d ){
	if( B_ind_d[j] <= R ){
	  sum += B_val_d[j];
	  count++;
	}
      }
    } else {
      FOR_LL( j , j_start , B_length_d ){
	if( B_ind_d[j] <= R ){
	  sum += B_val_d[j];
	  count++;
	} else {
	  j = B_length_d;
	}
      }
    }
    ll ( &C_val_d )[N_lim] = C_val[d];
    ll ( &C_ind_d )[N_lim] = C_ind[d];
    ll& C_length_d = C_length[d];
    j_start = -1;
    J = C_length_d / 2;
    while( J != 0 ){
      while( j_start + J < C_length_d ? C_ind_d[j_start + J] < L : false ){
	j_start += J;
      }
      J /= 2;
    }
    j_start++;
    FOR_LL( j , j_start , C_length_d ){
      if( C_ind_d[j] <= R ){
	ll& C_val_dj = C_val_d[j];
	sum += MIN( X , C_val_dj );
	count++;
      } else {
	j = C_length_d;
      }
    }
    sum += ( R - L + 1 - count ) * X;
    cout << sum << "\n";
  }
  return 0;
}
0