提出 #35493024

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ld = long double;
using pll = pair<ll, ll>;
// and so on
int arr[200001];
int vis[200001];
int cnt[300001];
vector<int> lst[2];
vector<pii> event;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N, Q;
    cin >> N >> Q;
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        if (0 <= arr[i] && arr[i] <= N) {
            cnt[arr[i]]++;
            vis[i] = 1;
            event.push_back({(N - arr[i] + (i - 1)) / i, i});
            lst[0].push_back(i);
        } else if (arr[i] < 0) {
            int na = -arr[i];
            event.push_back({(na + (i - 1)) / i, i});
            event.push_back({(N + 1 + na + (i - 1)) / i + 10, i});
        }
    }
    sort(event.begin(), event.end());
    int Mex = 0, ptr = 0;
    while (cnt[Mex] > 0) Mex++;
    for (int q = 1; q <= Q; q++) {
        int nxt = q % 2;
        int cunt = 1 - nxt;
        while (ptr < (int)event.size() && event[ptr].first == q) {
            int x = event[ptr].second;
            if (vis[x]++ == 0) lst[cunt].push_back(x);
            ptr++;
        }
        for (int x : lst[cunt]) {
            if (vis[x] == 1) lst[nxt].push_back(x);
        }
        lst[cunt].clear();
        for (int i : lst[nxt]) {
            if (0 <= arr[i] + (q - 1) * i && arr[i] + (q - 1) * i <= N) {
                if (--cnt[arr[i] + (q - 1) * i] == 0)
                    Mex = min(arr[i] + (q - 1) * i, Mex);
            }
            if (0 <= arr[i] + q * i && arr[i] + q * i <= N) {
                cnt[arr[i] + q * i]++;
                while (cnt[Mex] > 0) Mex++;
            }
        }
        
        cout << Mex << '\n';
    }
}

提出情報

ジャッジ結果