#981303 (C++23(gcc13)) No.649 ここでちょっとQK！

提出ソース

結果

問題	No.649 ここでちょっとQK！
ユーザー	しーぷら
提出日時	2024-05-12 13:23:42
言語	C++23(gcc13) (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	177 ms / 3,000 ms
コード長	12,743 bytes
コンパイル時間	6,328 ms
コンパイル使用メモリ	353,344 KB
実行使用メモリ	16,000 KB
最終ジャッジ日時	2024-05-12 13:23:55
合計ジャッジ時間	12,113 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	24 ms 6,944 KB
testcase_04	AC	173 ms 16,000 KB
testcase_05	AC	171 ms 16,000 KB
testcase_06	AC	177 ms 16,000 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	1 ms 6,944 KB
testcase_10	AC	1 ms 6,940 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	69 ms 8,448 KB
testcase_13	AC	67 ms 8,448 KB
testcase_14	AC	66 ms 8,576 KB
testcase_15	AC	70 ms 8,576 KB
testcase_16	AC	91 ms 9,216 KB
testcase_17	AC	77 ms 9,344 KB
testcase_18	AC	91 ms 9,856 KB
testcase_19	AC	96 ms 10,368 KB
testcase_20	AC	107 ms 10,880 KB
testcase_21	AC	117 ms 11,392 KB
testcase_22	AC	130 ms 11,776 KB
testcase_23	AC	124 ms 12,544 KB
testcase_24	AC	147 ms 12,928 KB
testcase_25	AC	155 ms 13,568 KB
testcase_26	AC	163 ms 13,952 KB
testcase_27	AC	2 ms 6,940 KB
testcase_28	AC	2 ms 6,940 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	53 ms 8,448 KB
testcase_31	AC	56 ms 8,832 KB
testcase_32	AC	2 ms 6,944 KB
testcase_33	AC	2 ms 6,940 KB
testcase_34	AC	1 ms 6,944 KB
testcase_35	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using namespace __gnu_pbds;
#ifdef Himesaka
#include <noachan.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif
// clang-format off
/* #language C++ GCC */
struct Init { Init() { ios::sync_with_stdio(0); cin.tie(0); cout << setprecision(13); } }init;
constexpr char nl = '\n';
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (lint i = lint(a); i < lint(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(a) (a).begin(), (a).end()
#define rall(x) (x).rbegin(), (x).rend()
#define SUM(v) accumulate(all(v), (ll)0)
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define pb push_back 
#define is insert
#define fi first
#define sc second
#define ifnot(x) if(!(x))
#define al(i, v) for (auto &i : v)
#define alm(ii,mm) for(auto ii=mm.begin();ii!=mm.end();ii++)
#define yes() cout << "Yes" << '\n'
#define no() cout << "No" << '\n'
#define yn(n) cout << ((n) ? "Yes" : "No") << '\n'
#define co() cout << nl;
#define len(c) (lint)(c).size()
#define inr(l, x, r) (l <= x && x <= r)
#define popcount(x) __builtin_popcountll(x)
typedef string str;typedef long long ll;typedef long long lint;typedef long double ld;typedef pair<lint,lint>pll;typedef pair<int,int>pii;typedef vector<int> vi;typedef vector<bool> vb;typedef vector<ld> vd;typedef vector<char> vc;typedef vector<ll> vl;typedef vector<str> vs;typedef vector<vector<int>> vvi;typedef vector<vector<ll>> vvl;typedef vector<vector<char>> vvc;typedef vector<vector<bool>> vvb;typedef vector<pll> vpl;template<class T>void snx(T &a){cin>>a;}void inz() {}template <class Head, class... Tail>void inz(Head &head, Tail &...tail){snx(head);inz(tail...);}
template <typename T>
using tree_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define scan(x) al(i, x) cin >> i
#define int_(...) int __VA_ARGS__;inz(__VA_ARGS__)
#define lint_(...) lint __VA_ARGS__;inz(__VA_ARGS__)
#define ld_(...) ld __VA_ARGS__;inz(__VA_ARGS__)
#define str_(...) string __VA_ARGS__;inz(__VA_ARGS__)
#define char_(...) char __VA_ARGS__;inz(__VA_ARGS__)
#define vi_(ne,sz) vi ne(sz);scan(ne);
#define vl_(ne,sz) vl ne(sz);scan(ne);
#define vb_(ne,sz) vb ne(sz);scan(ne);
#define vd_(ne,sz) vd ne(sz);scan(ne);
#define vc_(ne,sz) vc ne(sz);scan(ne);
#define vs_(ne,sz) vs ne(sz);scan(ne);
#define snn(h,w,a) rep(i,h)rep(j,w) cin >> a[i][j];
#define vvi_(ne,h,w) vvi ne(h,vi(w,0));snn(h,w,ne)
#define vvl_(ne,h,w) vvl ne(h,vl(w,0));snn(h,w,ne)
#define vvc_(ne,h,w) vvc ne(h,vc(w,0));snn(h,w,ne)
#define vvb_(ne,h,w) vvb ne(h,vb(w,0));snn(h,w,ne)
#define vpl_(ne,m) vpl ne(m); rep(i,m)cin>>ne[i].fi>>ne[i].sc;
ostream &operator<<(ostream &os, const vpl &v)
{for (auto &[e1, e2] : v){os << e1 << ' ' << e2 << endl;}return os;}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v){for (auto &e : v)os << e << ' ';return os;}
template <class T>
ostream &operator<<(ostream &os, const set<T> &v){for (auto &e : v)os << e << ' ';return os;}
template <class T>
ostream &operator<<(ostream &os, const multiset<T> &v){for (auto &e : v)os << e << ' ';return os;}
template <class T>
vector<T> &operator++(vector<T> &v) {al(e,v) e++;return v;}
template <class T>
vector<T> operator++(vector<T> &v, signed) {auto res = v;al(e,v) e++;return res;}
template <class T>
vector<T> &operator--(vector<T> &v) {al(e,v) e--;return v;}
template <class T>
vector<T> operator--(vector<T> &v, signed) {auto res = v;al(e,v) e--;return res;}
vector<pll> &operator--(vector<pll> &v) {al(e,v) e.fi--,e.sc--;return v;}
vector<pll> operator--(vector<pll> &v, signed) {auto res = v;al(e,v)e.fi--,e.sc--;return res;}
template<>
struct std::vector<bool>: std::basic_string<bool> {using std::basic_string<bool>::basic_string, std::basic_string<bool>::operator =;explicit vector(size_t n): vector(n, false) {}};
template <class T>
set<T> operator|(set<T> a, set<T> b){set<T> ret;set_union(all(a), all(b), inserter(ret, ret.begin()));return ret;}
template <class T>
multiset<T> operator|(multiset<T> a, multiset<T> b){multiset<T> ret;set_union(all(a), all(b), inserter(ret, ret.begin()));return ret;}
template <class T>
set<T> operator&(set<T> a, set<T> b){set<T> ret;set_intersection(all(a), all(b), inserter(ret, ret.begin()));return ret;}
template <class T>
multiset<T> operator&(multiset<T> a, multiset<T> b){multiset<T> ret;set_intersection(all(a), all(b), inserter(ret, ret.begin()));return ret;}
template <class T>
set<T> operator-(set<T> a, set<T> b){set<T> ret;set_symmetric_difference(all(a), all(b), inserter(ret, ret.begin()));return ret;}
template <class T>
multiset<T> operator-(multiset<T> a, multiset<T> b){multiset<T> ret;set_symmetric_difference(all(a), all(b), inserter(ret, ret.begin()));return ret;}
ostream &operator<<(ostream &os, const vvc &v)
{for (auto &e : v){for (auto &c : e)os << c;os << endl;}return os;}
ostream &operator<<(ostream &os, const vvl &v)
{for (auto &e : v){for (auto &c : e)os << c << ' ';os << endl;}return os;}
template <class... T>
void input(T &...a){(cin >> ... >> a);}
void out(){cout << '\n';}template <class T, class... Ts>void out(const T &a, const Ts &...b){cout << a;
(cout << ... << (cout << ' ', b));cout << '\n';}
void print(){cout << '\n';}template <class T, class... Ts>void print(const T &a, const Ts &...b){cout << a;
(cout << ... << (cout << ' ', b));cout << '\n';}
void exit_no(void){cout<<"No"<<nl; exit(0);};void exit_yes(void){cout<<"Yes"<<nl; exit(0);};
//template <class T> void exit_(T x){cout<<x<<nl; exit(0);};
void exit_(){cout << '\n';exit(0);}
template<class T, class... Ts>
void exit_(const T& a, const Ts&... b){cout << a;(cout << ... << (cout << ' ', b));cout << '\n';exit(0);}
template <class T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template <class T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }
template <class T>
void sort(T &v) {sort(all(v));}
template <class T>
void rsort(T &v) {sort(rall(v));}
template <class T>
void reverse(T &v) {reverse(all(v));}
template <class T> vector<T> ret_ex(vector<T> v){T n = len(v);vector<T> e(n + 1, 0);rep(i, 1, n + 1) e[i] = e[i - 1] + v[i - 1];return e;}
template<class T>
map<T,lint> count_v(vector<T> v){map<T,lint>res;al(x,v)res[x]++;return res;}
map<char,lint>count_s(str s) {map<char,lint>res;al(x,s)res[x]++;return res;}
template<class T,class U> bool is_out(T y,T x,U h,U w){return (y<0||y>=h||x<0||x>=w);}
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
const lint dx[8] = {1,0,-1,0,1,-1,-1,1},dy[8]={0,1,0,-1,1,1,-1,-1};
const int inf = INT_MAX/2;
const lint infl = 1LL<<60;
const ld PI = acos(-1.0);
template <class T>
vector<vector<T>> r_rot(vector<vector<T>> g)
{lint h = g.size(), w = g[0].size();vector<vector<T>> res(h, vector<T>(w));rep(i, h) rep(j, w) res[j][w - 1 - i] = g[i][j];return res;}
template <class T>
vector<vector<T>> l_rot(vector<vector<T>> g)
{lint h = g.size(), w = g[0].size();vector<vector<T>> res(h, vector<T>(w));rep(i, h) rep(j, w) res[w - 1 - j][i] = g[i][j];return res;}
set<pll> normalize_grid(vvc g){set<pll> se;rep(i, g.size()) rep(j, len(g[i])){if (g[i][j] == '#')se.is({i, j});}lint miy{infl}, mix{infl};al(x, se){chmin(miy, x.fi);chmin(mix, x.sc);}set<pll> ans;al(x, se)ans.is({x.fi - miy, x.sc - mix});return ans;}
multiset<pll> m_normalize_grid(vvc g){multiset<pll> se;rep(i, g.size()) rep(j, len(g[i])){if (g[i][j] == '#')se.is({i, j});}lint miy{infl}, mix{infl};al(x, se){chmin(miy, x.fi);chmin(mix, x.sc);}multiset<pll> ans;al(x, se)ans.is({x.fi - miy, x.sc - mix});return ans;}
set<pll> normalize_set(set<pll> se){lint miy{infl}, mix{infl};al(x, se){chmin(miy, x.fi);chmin(mix, x.sc);}set<pll> ans;al(x, se)ans.is({x.fi - miy, x.sc - mix});return ans;}
multiset<pll> m_normalize_set(multiset<pll> se){lint miy{infl}, mix{infl};al(x, se){chmin(miy, x.fi);chmin(mix, x.sc);}multiset<pll> ans;al(x, se)ans.is({x.fi - miy, x.sc - mix});return ans;}
bool NE(ld a, ld b){return abs(a - b) < DBL_EPSILON;}
template<class T> T pow_mod(T A, T N, T M) {T res = 1 % M;A %= M;while (N) {if (N & 1) res = (res * A) % M;A = (A * A) % M;N >>= 1;}return res;}
bool is_prime(ll N)
{if (N <= 1)return false;if (N == 2 || N == 3)return true;if (N % 2 == 0)return false;vl A = {2, 325, 9375, 28178, 450775,9780504, 1795265022};ll s = 0, d = N - 1;while (d % 2 == 0){++s;d >>= 1;}for (auto a : A){if (a % N == 0)return true;ll t, x = pow_mod<__int128_t>(a, d, N);if (x != 1){for (t = 0; t < s; ++t){if (x == N - 1)break;x = __int128_t(x) * x % N;}if (t == s)return false;}}return true;}
ll pollard(ll N)
{if (N % 2 == 0)return 2;if (is_prime(N))return N;auto f = [&](ll x) -> ll {return (__int128_t(x) * x + 1) % N;};ll step = 0;while (true){++step;ll x = step, y = f(x);while (true){ll p = gcd(y - x + N, N);if (p == 0 || p == N)break;if (p != 1)return p;x = f(x);y = f(f(y));}}}
vl prime_factorize(ll N){if (N == 1)return {};ll p = pollard(N);if (p == N)return {p};vl left = prime_factorize(p);vl right = prime_factorize(N / p);left.is(left.end(), right.begin(), right.end());sort(all(left));return left;}
vpl prime_fact(lint n)
{vl pr = prime_factorize(n);vpl ans{};rep(i, len(pr)){lint cnt{1}, num = pr[i];while (i + 1 < len(pr) && pr[i + 1] == num)cnt++, i++;ans.pb({num, cnt});}return ans;}
template<class T>
T d_pow(T x, T n)
{T ret = 1;while (n > 0){if (n & 1)ret *= x;x *= x;n >>= 1;}return ret;}
template<class T>
T digitnum(T x, T b = 10){T ret = 0; for(; x; x /= b) ret++; return ret;}
template<class T>
T digitsum(T x, T b = 10){T ret = 0; for(; x; x /= b) ret += x % b; return ret;}
template <class T, class U>
str to_baseB(T x, U b)
{str r{};while (x){lint n = x % b;r = (char)((n <= 9) ? ('0' + n) : ('A' + n - 10)) + r;x /= b;}return r;}
lint to_base10(str x, lint b = 10)
{lint r{}, base = 1;for (lint i = len(x) - 1; i >= 0; --i){lint n = ('0' <= x[i] && x[i] <= '9') ? (x[i] - '0') : (x[i] - 'A' + 10);r += base * n;base *= b;}return r;}
template<class T>
T nPr(T n, T r)
{T i, result = 1;rep(i, r) { result *= (T)(n - i); }return result;}
template<class T>
T nCr(T n, T r){T i,result = 1;rep(i, min(r, n - r)){result *= (T)(n - i);result /= (T)(i + 1);}return result;}
template <class T>
vector<T> div(T n){vector<T> ret;for (T i = 1; i * i <= n; i++)if (!(n % i)){ ret.pb(i);if (i * i != n) ret.pb(n / i);}sort(all(ret)); return ret;}
ll arith(ll x) { return x * (x + 1) / 2; }
ll arith2(ll a, ll d, ll n){return n * (2 * a + (n - 1) * d) / 2; }
vl sieve(lint n)
{vl res;vector<int> mem(n, 0);for (int i = 2; i < n; i++){if (mem[i]){continue;}res.push_back(i);for (int j = i; j < n; j += i){mem[j] = 1;}}return res;}
lint ret_dist(lint y1,lint x1,lint y2,lint x2){return powl(y2 - y1,2) + powl(x2 - x1,2);}
lint mgr(lint ok, lint ng, auto is_ok)
{while (abs(ok - ng) > 1){lint mid = (ok + ng) / 2;is_ok(mid) ? ok = mid : ng = mid;};return ok;}
ld mgr_double(ld ok, ld ng, auto is_ok)
{rep(_, 60){ld mid = (ok + ng) / 2;is_ok(mid) ? ok = mid : ng = mid;}return ok;}
// clang-format on
template <typename T>
class Comp
{
   vector<T> vals;
   vector<int> comp;

public:
   Comp(const vector<T> &data) : vals(data), comp(data.size())
   {
      sort(vals.begin(), vals.end());
      vals.erase(unique(vals.begin(), vals.end()), vals.end());
      for (int i = 0; i < comp.size(); i++)
         comp[i] = lower_bound(vals.begin(), vals.end(), data[i]) - vals.begin();
   }
   int get_index(T value)
   {
      auto lb = lower_bound(vals.begin(), vals.end(), value);
      assert(lb != vals.end() && *lb == value);
      return (int)(lb - vals.begin());
   }
   T get_value(size_t index)
   {
      return vals.at(index);
   }
   int operator[](size_t index) const
   {
      return comp.at(index);
   }
   vector<int> get_compressed_vector() const
   {
      return comp;
   }
   int size() const
   {
      return vals.size();
   }
};

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using tree_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main()
{
   tree_set<pll> se;
   lint_(q, k);
   lint cnt{};
   for (; q--;)
   {
      lint_(t);
      if (t == 1)
      {
         lint_(x);
         se.is({x, cnt++});
      }
      if (t == 2)
      {
         if (se.size() < k)
            out(-1);
         else
         {
            auto it = se.find_by_order(k - 1);
            out(it->fi);
            se.erase(it);
         }
      }
   }
}

yukicoder

結果

テストケース

ソースコード