Tikut

input/code.cpp: In function 'void solve()':
input/code.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3>, std::allocator<std::array<int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         while (j < evt.size() && evt[j][0] == i) {
      |                ~~^~~~~~~~~~~~

#include <bits/stdc++.h>
 
#define MODE 1
 
#if MODE
#define debug(x) cout << #x << ": " << (x) << endl
#define log(x) cout << (x) << endl
#define test(x) x
#else
#define debug(x)
#define log(x)
#define test(x)
#endif
 
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
#define X real()
#define Y imag()
 
using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using P = complex<ll>;
 
template<typename S, typename T = S> void chmin(S &s, T t) {s = s < t ? s : t;}
template<typename S, typename T = S> void chmax(S &s, T t) {s = s > t ? s : t;}
 
const ll M = 1000000007; // 998244353
 
void solve() {
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n);
    for (int &i : a) cin >> i;
    
    priority_queue<array<int, 3>> pq;
    vector<int> maxl(m+1), minl(m+1);
    
    minl[0] = 2e9;
    for (int i = 0; i < n; ++i) {
        chmin(minl[0], a[i]);
        pq.push({a[i]/2, a[i], 3});
    }
    
    for (int i = 1; i <= m; ++i) {
        auto a = pq.top();
        pq.pop();
        minl[i] = min(minl[i-1], a[0]);
        pq.push({a[1] / a[2], a[1], a[2] + 1});
    }
    
    for (int i = 0; i <= m; ++i) minl[i] *= -1;
    
    pq = priority_queue<array<int, 3>>();
    maxl[0] = 0;
    int cminl = 2e9;
    for (int i = 0; i < n; ++i) {
        chmax(maxl[0], a[i]);
        chmin(cminl, a[i]);
        pq.push({a[i], a[i], 2});
    }
    
    vector<array<int, 3>> evt;
    
    for (int i = 1; i <= m; ++i) {
        auto a = pq.top();
        pq.pop();
        maxl[i] = pq.size() ? max(pq.top()[0], (a[1] - 1) / a[2] + 1) : (a[1] - 1) / a[2] + 1;
        chmin(cminl, a[1] / a[2]);
        pq.push({(a[1] - 1) / a[2] + 1, a[1], a[2] + 1});
        
        int j = lower_bound(all(minl), -cminl) - minl.begin();
        chmax(j, i);
        evt.push_back({i, maxl[i] - cminl, 0});
        evt.push_back({j+1, maxl[i] - cminl, 1});
        evt.push_back({j+1, maxl[i], 2});
    }
    
    sort(all(evt));
    
    map<int, int> f;
    f[2e9] = 1;
    int j = 0;
    int cmaxl = 2e9;
    for (int i = 1; i <= m; ++i) {
        while (j < evt.size() && evt[j][0] == i) {
            if (evt[j][2] == 0) ++f[evt[j][1]];
            else if (evt[j][2] == 1) {
                if (--f[evt[j][1]] == 0) f.erase(evt[j][1]);
            } else chmin(cmaxl, evt[j][1]);
            ++j;
        }
        cout << min(f.begin()->fi, cmaxl + minl[i]) << " \n"[i == m];
    }
}
 
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    int t = 1;
    if (t == 0) cin >> t;
    while (t--) solve();
    
    return 0;
}

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