#514451 (C++17) No.1248 Kth Sum

• 問題: No.1248 Kth Sum
• ユーザー: 👑 tute7627
• 提出日時: 2020-07-19 15:33:00
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 894 ms / 2,000 ms
• コード長: 5,200 bytes
• コンパイル時間: 2,431 ms
• コンパイル使用メモリ: 225,032 KB
• 実行使用メモリ: 92,804 KB
• 最終ジャッジ日時: 2024-05-09 15:39:24
• 合計ジャッジ時間: 22,573 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	894 ms; 92,544 KB
testcase_14	AC	868 ms; 92,620 KB
testcase_15	AC	870 ms; 92,680 KB
testcase_16	AC	800 ms; 92,324 KB
testcase_17	AC	823 ms; 92,800 KB
testcase_18	AC	823 ms; 92,324 KB
testcase_19	AC	818 ms; 92,672 KB
testcase_20	AC	820 ms; 92,456 KB
testcase_21	AC	821 ms; 92,676 KB
testcase_22	AC	852 ms; 92,676 KB
testcase_23	AC	2 ms; 5,376 KB
testcase_24	AC	521 ms; 84,104 KB
testcase_25	AC	894 ms; 92,580 KB
testcase_26	AC	601 ms; 87,424 KB
testcase_27	AC	879 ms; 92,676 KB
testcase_28	AC	875 ms; 92,676 KB
testcase_29	AC	877 ms; 92,676 KB
testcase_30	AC	708 ms; 92,544 KB
testcase_31	AC	702 ms; 92,712 KB
testcase_32	AC	695 ms; 92,676 KB
testcase_33	AC	2 ms; 5,376 KB
testcase_34	AC	892 ms; 92,544 KB
testcase_35	AC	872 ms; 92,804 KB
testcase_36	AC	855 ms; 92,676 KB
testcase_37	AC	861 ms; 92,736 KB

ソースコード

//#define _GLIBCXX_DEBUG

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

#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD1 = 1e9+7;
const ll MOD9 = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,-1,0,0,1,1,-1,-1};
vector<ll>dy={0,0,1,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2>&p){
  return os << p.first << " " << p.second;
}
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
template<typename T, typename F>
struct DisjointSparseTable{
  int n;
  vector<vector<T>>data;
  const F func;
  DisjointSparseTable(vector<T>&v, const F &f):func(f),n(v.size()){
    int num=0;
    while((1<<num)<v.size())num++;
    data.assign(num+5,vector<T>(n+1, T()));
    if(n>=1)data[0][n-1]=v[n-1];
    for(int i=1;i<n;i++){
      int k = __builtin_ctz(i);
      data[k][i-1]=v[i-1];
      if(i!=n)data[k][i]=v[i];
      int l=i-(1<<k),r=min(n,i+(1<<k));
      for(int j=i-2;j>=l;j--)data[k][j]=func(v[j],data[k][j+1]);
      for(int j=i+1;j<r;j++)data[k][j]=func(data[k][j-1],v[j]);
    }
  }
  T query(int l,int r){//[l,r)
    r--;
    if(l==r)return data[0][l];
    ll k=31-__builtin_clz(l^r);
    return func(data[k][l],data[k][r]);
  }
};
template<typename T>
struct BIT{
  ll n;
  ll k=1;
  vector<T>data;
  BIT() = default;
  BIT(ll size):n(size){
    data.assign(n,0);
    while(k*2<=n)k*=2;
  }
  void add(ll a,T w){
    for(ll i=a+1;i<=n;i+=i&-i)data[i-1]+=w;
  }
  T sum(ll a){
	if(a<0)return 0;
    T ret = 0;
    for(ll i=a+1;i>0;i-=i&-i)ret+=data[i-1];
    return ret;
  }
  T sum(ll a,ll b){return a>b?0:sum(b)-sum(a-1);}
  T operator[](ll pos){
    return sum(pos,pos);
  }
  ll lower_bound(ll x){
    ll ret=0;    
    for(ll i=k;i>0;i/=2){
      if(ret+i<=n&&data[ret+i-1]<x){
        x-=data[ret+i-1];
        ret+=i;
      }
    }
    return ret;
  }
  void print(){
    for(ll i=0;i<n;i++){
      if(i!=0)cout<<" ";
      cout<<(*this)[i];
    }
    cout<<endl;
  }
};
template<typename T>
map<T,ll> compress(vector<T> &v){
  sort(ALL(v));
  v.erase(unique(ALL(v)),v.end());
  map<T, ll> ret;
  for(ll i=0;i<(ll)v.size();i++)
    ret[v[i]]=i;
  return ret;
}
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  ll n,k;cin>>n>>k;
  vector<ll>a(n);
  rep(i,0,n)cin>>a[i];
  auto f=[&](ll x,ll y){return min(x,y);};
  DisjointSparseTable<ll,decltype(f)>dst(a, f);
  map<ll,ll>mp;
  auto val=a;
  mp=compress(val);
  ll sz=mp.size();
  BIT<ll>sum(sz),bit(sz);
  vector<ll>ret=a;
  vector<vector<ll>>g(n);
  rep(i,1,n){
    for(ll j=i+1;j<n;j+=i){
      g[j].PB(i);
    }
  }
  rrep(i,0,n){
    bit.add(mp[a[i]],1);
    sum.add(mp[a[i]],a[i]);
    for(auto k:g[i]){
      ll m=(i+k-1)/k;
      ll x=k+i; //[i,x)から一つはとる
      ll y=(k+1)*m-1; //[y,n)から一つはとる
      if(y>=n)continue;
      ll mi1=dst.query(i,x);
      ll mi2=dst.query(y,n);
      ll idx=bit.lower_bound(m);
      ll s=sum.sum(0,idx);
      ll lastnum=bit.sum(idx,idx);
      ll allnum=bit.sum(0,idx);
      s-=val[idx]*(allnum-m);
      ll last1=val[idx];
      ll last2=val[bit.lower_bound(m-1)];
      if(mi1>mi2)swap(mi1,mi2);
      ll cand=0;
      if(mi1>last1)cand=s+mi2+mi1-last1-last2;
      else if(mi2>last1)cand=s+mi2-last1;
      else if(mi1==mi2&&last1==mi1&&last2!=mi2){
        cand=s+mi1-last2;
      }
      else cand=s;
      chmin(ret[k],cand);
    }
  }
  cout<<ret[k-1]<<endl;
  return 0;
}