#554955 (C++17) No.1233 割り切れない気持ち

提出ソース

結果

問題	No.1233 割り切れない気持ち
ユーザー	LayCurse
提出日時	2020-09-18 21:59:01
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	23 ms / 3,153 ms
コード長	8,656 bytes
コンパイル時間	2,528 ms
コンパイル使用メモリ	211,476 KB
実行使用メモリ	11,132 KB
最終ジャッジ日時	2023-09-04 21:47:31
合計ジャッジ時間	4,824 ms
ジャッジサーバーID （参考情報）	judge13 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	7 ms 9,340 KB
testcase_01	AC	7 ms 9,392 KB
testcase_02	AC	9 ms 9,544 KB
testcase_03	AC	11 ms 9,272 KB
testcase_04	AC	11 ms 9,440 KB
testcase_05	AC	9 ms 9,544 KB
testcase_06	AC	10 ms 9,352 KB
testcase_07	AC	15 ms 10,072 KB
testcase_08	AC	16 ms 10,164 KB
testcase_09	AC	20 ms 11,012 KB
testcase_10	AC	20 ms 10,912 KB
testcase_11	AC	14 ms 9,544 KB
testcase_12	AC	20 ms 10,860 KB
testcase_13	AC	20 ms 11,016 KB
testcase_14	AC	21 ms 10,852 KB
testcase_15	AC	21 ms 10,868 KB
testcase_16	AC	21 ms 10,860 KB
testcase_17	AC	9 ms 10,600 KB
testcase_18	AC	23 ms 10,908 KB
testcase_19	AC	11 ms 10,928 KB
testcase_20	AC	6 ms 7,412 KB
testcase_21	AC	10 ms 10,908 KB
testcase_22	AC	10 ms 10,972 KB
testcase_23	AC	10 ms 10,588 KB
testcase_24	AC	10 ms 11,024 KB
testcase_25	AC	9 ms 11,112 KB
testcase_26	AC	9 ms 11,132 KB
testcase_27	AC	10 ms 10,912 KB
testcase_28	AC	10 ms 10,928 KB
testcase_29	AC	10 ms 10,856 KB
testcase_30	AC	10 ms 10,996 KB
testcase_31	AC	10 ms 11,020 KB
testcase_32	AC	10 ms 10,848 KB
testcase_33	AC	10 ms 10,912 KB
testcase_34	AC	10 ms 10,952 KB
testcase_35	AC	10 ms 10,916 KB
testcase_36	AC	10 ms 10,864 KB
testcase_37	AC	6 ms 9,344 KB
testcase_38	AC	8 ms 10,384 KB
testcase_39	AC	16 ms 10,908 KB
testcase_40	AC	16 ms 10,932 KB

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

ソースコード

raw source code

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S min_L(S a,T b){
  return a<=b?a:b;
}
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(long long x){
  int s=0;
  int m=0;
  char f[20];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
template<class T> struct Arr1d{
  int n;
  int mem;
  T*d;
  T& operator[](int a){
    return d[a];
  }
  void sort(){
    reset();
    std::sort(d, d+n);
  }
  int set_cumulative_sum;
  int cumulative_sum_mem;
  T*cumulative_sum;
  void setSum(void){
    int i;
    set_cumulative_sum = 1;
    if(cumulative_sum_mem < n+1){
      delete[] cumulative_sum;
      cumulative_sum = new T[n+1];
      cumulative_sum_mem = n+1;
    }
    cumulative_sum[0] = 0;
    for(i=(0);i<(n);i++){
      cumulative_sum[i+1] = cumulative_sum[i] + d[i];
    }
  }
  T getSum(int i, int j){
    if(set_cumulative_sum==0){
      setSum();
    }
    return cumulative_sum[j+1] - cumulative_sum[i];
  }
  int set_const_len_left;
  int const_len_left_mem;
  int*const_len_left;
  void setConstLenLeft(void){
    int i;
    set_const_len_left = 1;
    if(const_len_left_mem < n){
      delete[] const_len_left;
      const_len_left = new int[n];
      const_len_left_mem = n;
    }
    for(i=(0);i<(n);i++){
      const_len_left[i] = 1;
    }
    for(i=(1);i<(n);i++){
      if(d[i]==d[i-1]){
        const_len_left[i] = const_len_left[i-1] + 1;
      }
    }
  }
  int ConstLenLeft(int st, T val){
    if(!set_const_len_left){
      setConstLenLeft();
    }
    if(val != d[st]){
      return 0;
    }
    return const_len_left[st];
  }
  int ConstLenLeft(int st){
    if(!set_const_len_left){
      setConstLenLeft();
    }
    return const_len_left[st];
  }
  int ConstLenLeftCyclic(int st, T val){
    if(!set_const_len_left){
      setConstLenLeft();
    }
    st %= n;
    if(st < 0){
      st += n;
    }
    if(val != d[st]){
      return 0;
    }
    if(const_len_left[st] != st+1 || d[st] != d[n-1]){
      return const_len_left[st];
    }
    if(const_len_left[n-1] == n){
      return 1073709056;
    }
    return const_len_left[st] + const_len_left[n-1];
  }
  int ConstLenLeftCyclic(int st){
    if(!set_const_len_left){
      setConstLenLeft();
    }
    st %= n;
    if(st < 0){
      st += n;
    }
    if(const_len_left[st] != st+1 || d[st] != d[n-1]){
      return const_len_left[st];
    }
    if(const_len_left[n-1] == n){
      return 1073709056;
    }
    return const_len_left[st] + const_len_left[n-1];
  }
  int set_const_len_right;
  int const_len_right_mem;
  int*const_len_right;
  void setConstLenRight(void){
    int i;
    set_const_len_right = 1;
    if(const_len_right_mem < n){
      delete[] const_len_right;
      const_len_right = new int[n];
      const_len_right_mem = n;
    }
    for(i=(0);i<(n);i++){
      const_len_right[i] = 1;
    }
    for(i=(n-1)-1;i>=(0);i--){
      if(d[i]==d[i+1]){
        const_len_right[i] = const_len_right[i+1] + 1;
      }
    }
  }
  int ConstLenRight(int st, T val){
    if(!set_const_len_right){
      setConstLenRight();
    }
    if(val != d[st]){
      return 0;
    }
    return const_len_right[st];
  }
  int ConstLenRight(int st){
    if(!set_const_len_right){
      setConstLenRight();
    }
    return const_len_right[st];
  }
  int ConstLenRightCyclic(int st, T val){
    if(!set_const_len_right){
      setConstLenRight();
    }
    if(val != d[st]){
      return 0;
    }
    st %= n;
    if(st < 0){
      st += n;
    }
    if(const_len_right[st] != n-st || d[st] != d[0]){
      return const_len_right[st];
    }
    if(const_len_right[0] == n){
      return 1073709056;
    }
    return const_len_right[st] + const_len_right[0];
  }
  int ConstLenRightCyclic(int st){
    if(!set_const_len_right){
      setConstLenRight();
    }
    st %= n;
    if(st < 0){
      st += n;
    }
    if(const_len_right[st] != n-st || d[st] != d[0]){
      return const_len_right[st];
    }
    if(const_len_right[0] == n){
      return 1073709056;
    }
    return const_len_right[st] + const_len_right[0];
  }
  int set_dhist;
  int dhist_mem;
  int*dhist;
  T dhist_mn;
  T dhist_mx;
  void setDHist(void){
    int i;
    int len;
    set_dhist = 1;
    if(n==0){
      return;
    }
    dhist_mn = dhist_mx = d[0];
    for(i=(1);i<(n);i++){
      if(dhist_mn > d[i]){
        dhist_mn = d[i];
      }
      if(dhist_mx < d[i]){
        dhist_mx = d[i];
      }
    }
    len = dhist_mx - dhist_mn + 1;
    if(dhist_mem < len){
      delete[] dhist;
      dhist = new int[len];
      dhist_mem = len;
    }
    for(i=(0);i<(len);i++){
      dhist[i] = 0;
    }
    for(i=(0);i<(n);i++){
      dhist[d[i] - dhist_mn]++;
    }
  }
  int dHist(T x){
    if(set_dhist==0){
      setDHist();
    }
    if(n == 0 || x < dhist_mn || x > dhist_mx){
      return 0;
    }
    return dhist[x - dhist_mn];
  }
  void reset(){
    set_cumulative_sum = 0;
    set_const_len_left = 0;
    set_const_len_right = 0;
    set_dhist = 0;
  }
  void memory_expand(int nn){
    if(mem < nn){
      delete[] d;
      d = new T[nn];
      mem = nn;
    }
  }
  void malloc(int nn){
    reset();
    memory_expand(nn);
    n = nn;
  }
  void setN(int nn){
    reset();
    memory_expand(nn);
    n = nn;
  }
  void free(){
    destructor();
  }
  void constructor(){
    n = mem = 0;
    d = NULL;
    set_cumulative_sum = 0;
    cumulative_sum_mem = 0;
    cumulative_sum = NULL;
    set_const_len_left = 0;
    const_len_left_mem = 0;
    const_len_left = NULL;
    set_const_len_right = 0;
    const_len_right_mem = 0;
    const_len_right = NULL;
    set_dhist = 0;
    dhist_mem = 0;
    dhist = NULL;
  }
  void constructor(int nn){
    constructor();
    malloc(nn);
  }
  void destructor(){
    delete[] d;
    d = NULL;
    mem = n = 0;
    set_cumulative_sum = 0;
    cumulative_sum_mem = 0;
    delete[] cumulative_sum;
    cumulative_sum = NULL;
    set_const_len_left = 0;
    const_len_left_mem = 0;
    delete[] const_len_left;
    const_len_left = NULL;
    set_const_len_right = 0;
    const_len_right_mem = 0;
    delete[] const_len_right;
    const_len_right = NULL;
    set_dhist = 0;
    dhist_mem = 0;
    delete[] dhist;
    dhist = NULL;
  }
  Arr1d(){
    constructor();
  }
  Arr1d(int nn){
    constructor(nn);
  }
  ~Arr1d(){
    destructor();
  }
}
;
int N;
int A[200000];
Arr1d<long long> h(200000+1);
Arr1d<long long> x(200000+1);
int main(){
  int i;
  int j;
  int k;
  long long res = 0;
  long long tmp;
  rd(N);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
      rd(A[Lj4PdHRW]);
    }
  }
  for(i=(0);i<(200000+1);i++){
    h[i] = x[i] = 0;
  }
  for(i=(0);i<(N);i++){
    h[A[i]]++;
  }
  for(i=(0);i<(N);i++){
    x[A[i]] += A[i];
  }
  for(i=(2);i<(200000+1);i++){
    if(h[i]){
      for(j=(0);j<(200000+1);j+=(i)){
        k =min_L(j+i, 200000+1);
        tmp = x.getSum(j,k-1) - j*h.getSum(j,k-1);
        res += h[i] * tmp;
      }
    }
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20200916-1

// --- original code ---
// int N, A[2d5];
// Arr1d<ll> h(2d5+1);
// Arr1d<ll> x(2d5+1);
// {
//   int i, j, k;
//   ll res = 0, tmp;
//   rd(N,A(N));
//   rep(i,2d5+1) h[i] = x[i] = 0;
//   rep(i,N) h[A[i]]++;
//   rep(i,N) x[A[i]] += A[i];
// 
//   rep(i,2,2d5+1) if(h[i]){
//     rep(j,0,2d5+1,i){
//       k = min(j+i, 2d5+1);
//       tmp = x.getSum(j,k-1) - j*h.getSum(j,k-1);
//       res += h[i] * tmp;
//     }
//   }
// 
//   wt(res);
// }

yukicoder

結果

テストケース

ソースコード