Submission #68421486

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    if (!(cin >> N >> Q)) return 0;
    const int VMAX = 1'000'000; // A_i, B_j の上限
    vector<long long> cnt(VMAX + 1, 0);
    int maxA = 0;
    for (int i = 0; i < N; ++i) {
        int a; cin >> a;
        cnt[a]++;
        if (a > maxA) maxA = a;
    }
    // 前計算
    vector<long long> PC(VMAX + 1, 0), PS(VMAX + 1, 0);
    for (int v = 1; v <= VMAX; ++v) {
        PC[v] = PC[v-1] + cnt[v];
        PS[v] = PS[v-1] + 1LL * v * cnt[v];
    }
    long long S = PS[VMAX];

    auto T_of_b = [&](int b)->long long {
        long long t = b - 1;            // 上限
        int ti = (int)min<long long>(t, VMAX);
        long long leftCnt = PC[ti], leftSum = PS[ti];
        // v > t の数は N - leftCnt。t が VMAX を超えてもここは 0 になる
        return leftSum + t * ( (long long)N - leftCnt );
    };

    for (int qi = 0; qi < Q; ++qi) {
        int b; cin >> b;
        if (b > maxA) {                 // そもそも同一フレーバー b 個が存在し得ない
            cout << -1 << '\n';
            continue;
        }
        long long T = T_of_b(b);
        long long ans = max<long long>(b, T + 1);
        if (ans > S) cout << -1 << '\n'; // 形式的な保険
        else cout << ans << '\n';
    }
    return 0;
}

Submission Info

Judge Result