Tikut

input/code.cpp: In function 'int main()':
input/code.cpp:12:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     for(auto&x:a){ scanf("%lld",&x); maxA=max(maxA,x); minA=min(minA,x); sumA+=x; }
      |                    ~~~~~^~~~~~~~~~~

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)4e18;

int main(){
    int n; ll mm;
    if(scanf("%d %lld",&n,&mm)!=2) return 0;
    int M=(int)mm;
    vector<ll> a(n);
    ll maxA=0, minA=INF, sumA=0;
    for(auto&x:a){ scanf("%lld",&x); maxA=max(maxA,x); minA=min(minA,x); sumA+=x; }

    // ---------- f(n+k), k=1..M : min possible max-piece (greedy: cut current max) ----------
    // heap of {ceil(a/c), a, c}, max by first
    priority_queue<array<ll,3>> pq;
    for(ll x:a) pq.push({x, x, 1});            // ceil(x/1)=x
    vector<ll> fval(M+1);
    for(int k=1;k<=M;k++){
        auto t=pq.top(); pq.pop();
        ll ai=t[1], ci=t[2]+1;
        ll c=(ai+ci-1)/ci;                     // ceil(ai/ci)
        pq.push({c, ai, ci});
        fval[k]=pq.top()[0];
    }

    // ---------- g(n+k), k=1..M : max possible min-piece ----------
    // g(N) = max Y in [1,minA] with Sfloor(Y)=sum floor(a_i/Y) >= N
    auto Sfloor=[&](ll Y)->ll{ ll s=0; for(ll x:a) s+=x/Y; return s; };
    vector<ll> gval(M+1);
    {
        // Yhi = g(n+1)
        ll lo=1, hi=minA, Yhi=1;
        while(lo<=hi){ ll mid=lo+(hi-lo)/2; if(Sfloor(mid)>=n+1){ Yhi=mid; lo=mid+1;} else hi=mid-1; }
        ll base=Sfloor(Yhi);
        ll target=(ll)n+M;
        vector<ll> v(n);
        // max-PQ of next (lower) breakpoint Y
        priority_queue<pair<ll,int>> epq;
        for(int i=0;i<n;i++){ v[i]=a[i]/Yhi; ll ny=a[i]/(v[i]+1); epq.push({ny,i}); }
        ll curY=Yhi, curS=base, pS=n;
        auto fill=[&](ll y, ll Sval){
            ll loN=pS+1, hiN=min(Sval,target);
            for(ll N=loN; N<=hiN; N++) gval[(int)(N-n)]=y;
            if(Sval>pS) pS=Sval;
        };
        fill(curY,curS);
        while(pS<target && !epq.empty()){
            ll t=epq.top().first;
            if(t<1) break;
            while(!epq.empty() && epq.top().first==t){
                int i=epq.top().second; epq.pop();
                ll newv=a[i]/t;
                curS += (newv - v[i]);
                v[i]=newv;
                ll ny=a[i]/(newv+1);
                if(newv+1<=a[i]) epq.push({ny,i});
            }
            curY=t;
            fill(curY,curS);
        }
    }

    // ---------- Y2(R) = min_i floor(a_i/ceil(a_i/R)) as step function over R>=Rmin ----------
    ll Rmin=fval[M];
    vector<ll> segLo, segY;
    {
        vector<ll> k(n), V(n);
        multiset<ll> ms;
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> epq; // min next-change R
        for(int i=0;i<n;i++){
            k[i]=(a[i]+Rmin-1)/Rmin;           // ceil
            V[i]=a[i]/k[i];
            ms.insert(V[i]);
            ll nx=(k[i]>=2)?(a[i]+(k[i]-1)-1)/(k[i]-1):INF;
            epq.push({nx,i});
        }
        segLo.push_back(Rmin); segY.push_back(*ms.begin());
        while(!epq.empty()){
            ll t=epq.top().first;
            if(t==INF || t>maxA) break;
            while(!epq.empty() && epq.top().first==t){
                int i=epq.top().second; epq.pop();
                ms.erase(ms.find(V[i]));
                k[i]-=1;
                V[i]=a[i]/k[i];
                ms.insert(V[i]);
                ll nx=(k[i]>=2)?(a[i]+(k[i]-1)-1)/(k[i]-1):INF;
                epq.push({nx,i});
            }
            segLo.push_back(t); segY.push_back(*ms.begin());
        }
    }
    int S=segLo.size();

    // ---------- sparse table on D[j]=segLo[j]-segY[j] ----------
    vector<ll> D(S);
    for(int j=0;j<S;j++) D[j]=segLo[j]-segY[j];
    int LOG=1; while((1<<LOG)<S) LOG++; LOG++;
    vector<vector<ll>> sp(LOG, vector<ll>(S));
    sp[0]=D;
    for(int p=1;p<LOG;p++)
        for(int i=0;i+(1<<p)<=S;i++)
            sp[p][i]=min(sp[p-1][i], sp[p-1][i+(1<<(p-1))]);
    auto rmin=[&](int l,int r)->ll{ // inclusive, assumes l<=r
        int p=31-__builtin_clz(r-l+1);
        return min(sp[p][l], sp[p][r-(1<<p)+1]);
    };

    // ---------- answer each N ----------
    // answer(N)=min over R>=A of max(R-B, R-Y2(R)), A=f(N), B=g(N)
    string out;
    out.reserve((size_t)M*7);
    for(int k=1;k<=M;k++){
        ll A=fval[k], B=gval[k];
        // jA = last index with segLo<=A
        int jA=(int)(upper_bound(segLo.begin(),segLo.end(),A)-segLo.begin())-1;
        ll ans = A - min(B, segY[jA]);
        // jb = first index with segY > B
        int jb=(int)(upper_bound(segY.begin(),segY.end(),B)-segY.begin());
        // segments j in [jA+1, min(jb-1,S-1)] : segY<=B  -> D[j]
        int lo1=jA+1, hi1=min(jb-1,S-1);
        if(lo1<=hi1) ans=min(ans, rmin(lo1,hi1));
        // segments j in [max(jA+1,jb), S-1] : segY>B -> segLo[j]-B, min at smallest j
        int j0=max(jA+1,jb);
        if(j0<=S-1) ans=min(ans, segLo[j0]-B);
        out += to_string(ans);
        out += (k<M?' ':'\n');
    }
    fputs(out.c_str(), stdout);
    return 0;
}

Test 1

Subtask: 1, 3, 4, 5, 6

Verdict: ACCEPTED

Test 2

Subtask: 1, 4, 5, 6

Verdict: ACCEPTED

Test 3

Subtask: 1, 4, 5, 6

Verdict: ACCEPTED

Test 4

Subtask: 1, 4, 5, 6

Verdict: ACCEPTED

Test 5

Subtask: 2, 5, 6

Verdict: ACCEPTED

Test 6

Subtask: 2, 5, 6

Verdict: ACCEPTED

Test 7

Subtask: 3, 5, 6

Verdict: ACCEPTED

Test 8

Subtask: 3, 5, 6

Verdict: ACCEPTED

Test 9

Subtask: 3, 5, 6

Verdict: ACCEPTED

Test 10

Subtask: 3, 5, 6

Verdict: ACCEPTED

Test 11

Subtask: 3, 5, 6

Verdict: ACCEPTED

Test 12

Subtask: 4, 5, 6

Verdict: ACCEPTED

Test 13

Subtask: 4, 5, 6

Verdict: ACCEPTED

Test 14

Subtask: 4, 5, 6

Verdict: ACCEPTED

Test 15

Subtask: 4, 5, 6

Verdict: ACCEPTED

Test 16

Subtask: 5, 6

Verdict: ACCEPTED

Test 17

Subtask: 5, 6

Verdict: ACCEPTED

Test 18

Subtask: 5, 6

Verdict: ACCEPTED

Test 19

Subtask: 5, 6

Verdict: ACCEPTED

Test 20

Subtask: 6

Verdict: ACCEPTED

Test 21

Subtask: 6

Verdict: ACCEPTED

Test 22

Subtask: 6

Verdict: ACCEPTED