結果
問題 | No.649 ここでちょっとQK! |
ユーザー | あ |
提出日時 | 2024-09-23 03:35:12 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 265 ms / 3,000 ms |
コード長 | 5,981 bytes |
コンパイル時間 | 4,005 ms |
コンパイル使用メモリ | 274,464 KB |
実行使用メモリ | 12,616 KB |
最終ジャッジ日時 | 2024-09-23 03:35:24 |
合計ジャッジ時間 | 9,817 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,812 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 265 ms
6,940 KB |
testcase_04 | AC | 131 ms
12,564 KB |
testcase_05 | AC | 133 ms
12,616 KB |
testcase_06 | AC | 63 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 124 ms
7,672 KB |
testcase_13 | AC | 125 ms
7,536 KB |
testcase_14 | AC | 124 ms
7,664 KB |
testcase_15 | AC | 118 ms
7,540 KB |
testcase_16 | AC | 101 ms
7,668 KB |
testcase_17 | AC | 121 ms
8,124 KB |
testcase_18 | AC | 133 ms
8,592 KB |
testcase_19 | AC | 148 ms
8,924 KB |
testcase_20 | AC | 162 ms
9,388 KB |
testcase_21 | AC | 180 ms
9,720 KB |
testcase_22 | AC | 193 ms
10,308 KB |
testcase_23 | AC | 209 ms
10,648 KB |
testcase_24 | AC | 222 ms
11,108 KB |
testcase_25 | AC | 242 ms
11,492 KB |
testcase_26 | AC | 254 ms
11,796 KB |
testcase_27 | AC | 3 ms
6,940 KB |
testcase_28 | AC | 2 ms
6,940 KB |
testcase_29 | AC | 3 ms
6,944 KB |
testcase_30 | AC | 106 ms
6,944 KB |
testcase_31 | AC | 93 ms
6,944 KB |
testcase_32 | AC | 2 ms
6,944 KB |
testcase_33 | AC | 2 ms
6,940 KB |
testcase_34 | AC | 2 ms
6,940 KB |
testcase_35 | AC | 2 ms
6,940 KB |
ソースコード
#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*l;}) : 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); } } }