結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー あ
提出日時 2024-09-23 03:35:56
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 270 ms / 3,000 ms
コード長 5,979 bytes
コンパイル時間 3,753 ms
コンパイル使用メモリ 276,156 KB
実行使用メモリ 12,784 KB
最終ジャッジ日時 2024-09-23 03:36:08
合計ジャッジ時間 8,654 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

// clang-format off
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

struct Init { Init() { ios::sync_with_stdio(0); cin.tie(0); } } init;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define REP(i, a, b) for (int i = (a); i <= (b); i++)
#define DREP(i, a, b) for (int i = (a); i >= (b); i--)

#define all(x) (x).begin(), (x).end()

#define ingrid(x, y, H, W) (0 <= (x) && (x) < (H) && 0 <= (y) && (y) < (W))

#define input(A, i, j) for (int indx = (i); indx <= (j); indx++) cin >> A[indx];
#define output(A, i, j) for (int indx = (i); indx <= (j); indx++) cout << A[indx] << " ";

#define Yes(b) ((b) ? "Yes" : "No")
#define pb push_back
#define mp make_pair

using ll = long long;
using ull = unsigned long long;

using pii = pair<int, int>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;

using vb = vector<bool>;
using vi = vector<int>;
using vu = vector<unsigned>;
using vll = vector<long long>;
using vull = vector<unsigned long long>;

using Graph = vector<vector<int>>;

const ull mod = 998244353ull;
const ull MOD = 1000000007ull;


using lll = __int128_t;
using ulll = __uint128_t;
using vlll = vector<__int128_t>;
using vulll = vector<__uint128_t>;

void print(lll a) {
    string s = "";
    if (a==0) {
        s="0";
    } else {
        while (a>0) {
            s = (char)('0'+(int)(a%10))+s;
            a/=10;
        }
    }
    cout << s;
    return;
}

template <typename T> inline bool chmin(T &a, const T &b) { bool c = a > b;
    if (a > b)
        a = b;
    return c;
}
template <typename T> inline bool chmax(T &a, const T &b) {
    bool c = a < b;
    if (a < b)
        a = b;
    return c;
}
template <typename T> inline T ceil(T a, T b) { return (a + (b - 1)) / b; }
template <typename T> inline T floor(T a, T b) { return a / b; }

class UnionFind {
  public:
    vector<ll> par, rank;

    UnionFind(ll n) {
        par.resize(n, 0ll);
        rank.resize(n, 0ll);
        for (ll i = 0; i < n; i++)
            par[i] = i;
        }
    ll root(ll x) { return x == par[x] ? x : (par[x] = root(par[x])); }
    bool same(ll x, ll y) { return root(x) == root(y); }
    void unite(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (rank[x] < rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rank[x] == rank[y])
                rank[x]++;
        }
    }
};

template <typename X, typename M> struct SegLazy {
    vector<X> dat;
    vector<M> lazy;
    using fX  = function<X(X, X)>;
    using fXM = function<X(X, M)>;
    using fM  = function<M(M, M)>;
    using fP  = function<M(M,int)>;
    fX fx;
    fXM fxm;
    fM fm;
    X ex;
    M em;
    fP fp;
    int n;
    SegLazy(int _n, fX _fx, X _ex, fM _fm, M _em, fXM _fxm,
        fP _fp = [](M a, int l) -> M {return a;})
        : fx(_fx), ex(_ex), fm(_fm), em(_em), fxm(_fxm), fp(_fp), dat(_n * 4, _ex),
          lazy(_n * 4, _em) {
        int x = 1;
        while (x < _n)
            x  *= 2;
        n = x;
    }
    void set(int i, X x) { dat[i + n - 1] = x; }
    void eval(int k,int l) {
        if (lazy[k] == em) {
            return;
        } else if (k <= n - 2) {
            lazy[k * 2 + 1] = fm(lazy[k * 2 + 1], lazy[k]);
            lazy[k * 2 + 2] = fm(lazy[k * 2 + 2], lazy[k]);
        }
        dat[k]  = fxm(dat[k], fp(lazy[k],l));
        lazy[k] = em;
    }

    void update(void) {
        for (int i = n - 2; i >= 0; i--) {
            dat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }
    int find(X x) {
        int a = -1;
        int b = n;
        while (b > a+1) {
            if (query(0, (a+b)/2+1) >= x) {
                b = (a+b)/2;
            } else {
                a = (a+b)/2;
            }
        }
        return b;
    }
    X query(int a, int b) { return query_sub(a, b, 0, 0, n); }
    void update(int a, int b, M m) { update_sub(a, b, m, 0, 0, n); }

  private:
    X query_sub(int a, int b, int k, int l, int r) {
        eval(k, r-l);
        if (a <= l && r <= b) {
            return dat[k];
        } else if (r <= a || b <= l) {
            return ex;
        } else {
            X L = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            X R = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return fx(L, R);
        }
    }
    void update_sub(int a, int b, M m, int k, int l, int r) {
        eval(k,r-l);
        if (a <= l && r <= b) {
            lazy[k] = fm(lazy[k], m);
            eval(k,r-l);
        } else if (l < b && a < r) {
            update_sub(a, b, m, k*2+1, l, (l + r) / 2);
            update_sub(a, b, m, k*2+2, (l + r) / 2, r);
            dat[k] = fx(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
};
// clang-format on

int main() {
    int Q, K;
    cin >> Q >> K;
    vll q(Q);
    vll comp;
    rep(i, Q) {
        int f;
        ll v;
        cin >> f;
        if (f == 1) {
            cin >> v;
            q[i] = v;
            comp.pb(v);

        } else {
            q[i] = -1;
        }
    }
    sort(all(comp));
    comp.erase(unique(all(comp)), comp.end());
    int N = (int) comp.size();
    rep(i, Q) {
        if (q[i] != -1) {
            q[i] = (int) (lower_bound(all(comp), q[i]) - comp.begin());
        }
    }
    function<int(int, int)> fx = [](int a, int b) -> int {return a+b;};
    int ex = 0;
    function<int(int, int)> fm = [](int a, int b) -> int {return a+b;};
    int em = 0;
    function<int(int, int)> fxm = [](int a, int b) -> int {return a+b;};
    SegLazy<int, int> SL(N+2, fx, ex, fm, em, fxm);
    rep(i, Q) {
        if (q[i]==-1) {
            if (SL.query(0, N) < K) {
                cout  << -1 << endl;
            } else {
                int a = SL.find(K);
                cout << comp[a] << endl;
                SL.update(a, a+1, -1);
            }
        } else {
            SL.update(q[i], q[i]+1, 1);
        }
    }
}
0