Tikut

// #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>
 
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];
 
}
mt19937_64 gen(random_device{}());
uniform_int_distribution<int> dist(1, 1);
 
int random(int a, int b) {
    dist.param(uniform_int_distribution<int>::param_type(a, b));
    return dist(gen);
}
void solve() {
    int n = 5, m =100;
    cin >> n >> m;
    vector<int> a(n);
    for (auto &u: a) cin >> u;
    // for (auto &u: a) u = random(1, 1000);
    vector<array<int, 3>> maxs, mins;
    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, 2>> 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});
        difs.insert({nxt_mx-nxt_mn});
 
        while (under.size() && (*under.begin())[0]>=mn) {
            auto [x, y] = *under.begin();
            difs.erase(difs.find(y-x));
            under.erase(under.begin());
            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: WRONG ANSWER

Test 18

Group: 5, 6

Verdict: ACCEPTED

Test 19

Group: 5, 6

Verdict: ACCEPTED

Test 20

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 6

Verdict: RUNTIME ERROR

Test 22

Group: 6

Verdict: RUNTIME ERROR