1852C - Ina of the Mountain - CodeForces Solution

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
//#pragma GCC target("popcnt")
using namespace std;
#define int long long
int ttt;
int n;int K;
int ar[500005];



void solve(){
cin>>n>>K;
for(int i=1;i<=n;i++){
    cin>>ar[i];
    ar[i]%=K;
}
priority_queue<int,vector<int>,greater<int>>pq;
int ans=0;
int nw=0;
for(int i=1;i<=n;i++){
int dv=nw/K;
//if(ar[i]!=0){
//if(ar[i]==ar[i-1]&&i>=2){continue;}
    if(ar[i]<=nw){
        int v=dv*K+ar[i];
        if(v<=nw){
            pq.push((dv+1)*K+ar[i]-nw);
          //  cout<<(dv+1)*K+ar[i]-nw<<" ";
            nw=v;
        }else{
            pq.push(dv*K+ar[i]-nw);
        //    cout<<dv*K+ar[i]-nw<<" ";
            v=(dv-1)*K+ar[i];
            nw=v;
        }
    }else{
        int v=ar[i];
        int c=v-nw;
        if(pq.size()&&pq.top()<c){
            c=pq.top();
            pq.pop();
            pq.push(v-nw);
        }
        nw=ar[i];
        ans+=c;
    }
//}
//cout<<nw<<" "<<ans<<endl;


}
cout<<ans<<endl;


}


signed main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
cin>>ttt;
while(ttt--)solve();



}