Tikut

input/code.cpp: In function 'void solve()':
input/code.cpp:54:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |     while (maxs.size()<=m) {
      |            ~~~~~~~~~~~^~~
input/code.cpp:65:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |     while (mins.size()<=m) {
      |            ~~~~~~~~~~~^~~

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <algorithm>
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <queue>
 
using namespace std;
using namespace __gnu_pbds;
 
template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
 
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
// const ll M = 998244353;
const ll M = 1e9 + 7;
// ll M;
 
 
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define PI 3.141592653589793238462643383279502884L
 
const ll INFL = 1e18;
const int INF = 1e9;
const ll maxN = 5e5+1;
 
 
bool comp(array<int, 3> l, array<int, 3> r) {
    if (l[0]==r[0]) {
        return l[2]<r[2];
    } return l[0]>r[0];
 
}
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto &u: a) cin >> u;
    vector<array<int, 3>> maxs, mins;
    priority_queue<array<int, 3>> nxt;
    for (int i=0; i<n; i++) {
        nxt.push({a[i], i, 1});
    }
    while (maxs.size()<=m) {
        auto [_, idx, cnt] = nxt.top();
        maxs.push_back(nxt.top());
        nxt.pop();
        cnt++;
        nxt.push({(a[idx]+cnt-1)/cnt, idx, cnt});
    }
    nxt = priority_queue<array<int, 3>>();
    for (int i=0; i<n; i++) {
        nxt.push({a[i]/2, i, 2});
    }
    while (mins.size()<=m) {
        auto [_, idx, cnt] = nxt.top();
        mins.push_back(nxt.top());
        nxt.pop();
        cnt++;
        nxt.push({a[idx]/cnt, idx, cnt});
    }
 
 
 
    // for (int i=0; i<n; i++) {
    //     for (int j=1; j<=m+1; j++) {
    //         maxs.push_back({(a[i]+j-1)/j, i, j});
    //         if (j!=1) mins.push_back({a[i]/j, i, j});
    //     }
    // }
    // sort(all(maxs), comp);
    // sort(all(mins), comp);
    // maxs.resize(m+1);
    // mins.resize(m+1);
    multiset<int> difs;
    set<array<int, 3>> under;
    int mx = *max_element(all(a));
    int mn = *min_element(all(a));
    int nxt_mn = mn;
    for (int k=0; k<m; k++) {
        int idx = maxs[k][1];
        mn = min(mins[k][0], mn);
        nxt_mn = min(nxt_mn, a[idx]/(maxs[k][2]+1));
        nxt_mn = min(nxt_mn, mn);
        int nxt_mx = maxs[k+1][0];
        under.insert({nxt_mn, nxt_mx, k});
        difs.insert(nxt_mx-nxt_mn);
 
        while (under.size() && (*under.rbegin())[0]>=mn) {
            auto [x, y, _] = *under.rbegin();
            difs.erase(difs.find(y-x));
            under.erase(--under.end());
            mx = min(mx, y);
        }
        int ans = (mx-mn);
        if (difs.size()) ans = min(ans, *difs.begin());
        cout << ans << ' ';
    }
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    cout << setprecision(12);
 
 
    int tc = 1;
    // cin >>tc;
    while (tc--) solve();
 
}
 

Test 1

Group: 1, 3, 4, 5, 6

Verdict: ACCEPTED

Test 2

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 3

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 4

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 5

Group: 2, 5, 6

Verdict: ACCEPTED

Test 6

Group: 2, 5, 6

Verdict: ACCEPTED

Test 7

Group: 3, 5, 6

Verdict: ACCEPTED

Test 8

Group: 3, 5, 6

Verdict: ACCEPTED

Test 9

Group: 3, 5, 6

Verdict: ACCEPTED

Test 10

Group: 3, 5, 6

Verdict: ACCEPTED

Test 11

Group: 3, 5, 6

Verdict: ACCEPTED

Test 12

Group: 4, 5, 6

Verdict: ACCEPTED

Test 13

Group: 4, 5, 6

Verdict: ACCEPTED

Test 14

Group: 4, 5, 6

Verdict: ACCEPTED

Test 15

Group: 4, 5, 6

Verdict: ACCEPTED

Test 16

Group: 5, 6

Verdict: ACCEPTED

Test 17

Group: 5, 6

Verdict: ACCEPTED

Test 18

Group: 5, 6

Verdict: ACCEPTED

Test 19

Group: 5, 6

Verdict: ACCEPTED

Test 20

Group: 6

Verdict: ACCEPTED

Test 21

Group: 6

Verdict: ACCEPTED

Test 22

Group: 6

Verdict: ACCEPTED