結果

問題 No.649 ここでちょっとQK!
ユーザー f1b_maxbl00df1b_maxbl00d
提出日時 2021-01-19 07:22:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,051 ms / 3,000 ms
コード長 6,525 bytes
コンパイル時間 5,132 ms
コンパイル使用メモリ 331,388 KB
最終ジャッジ日時 2025-01-18 02:30:19
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

//#pragma warning(disable:4996)
//#include <Windows.h>
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>
//#include <stdio.h>
//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
typedef long long LL;
typedef long double LD;
typedef boost::multiprecision::cpp_int bigint;
typedef pair<LL, LL> PLL;
typedef pair<int, int> PI;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef unsigned long long ULL;
template<class T>
using pqueue = priority_queue<T, vector<T>, function<bool(T, T)>>;
template<class T>
inline void chmin(T& a, T b) {
a = min(a, b);
}
template<class T>
inline void chmax(T& a, T b) {
a = max(a, b);
}
void input();
void solve();
void daminput();
void naive();
void outputinput();
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
input();
//daminput();
solve();
//naive();
//outputinput();
return 0;
}
//////////////////////////////////////////////////
//////////////////////////////////////////////////
void input() {
}
void daminput() {
}
//class Rng {
//public:
// Rng();
// friend ostream operator<<(ostream&,Rng); (if print neccesary)
//};
//Rng operator+(Rng, Rng);
class T {
public:
LL v;
T() :v(1e7) {};
T(LL _v) :v(_v) {};
};
T operator+(T a, T b) {
if (a.v < b.v)return b;
else return a;
}
//treap
//Xorshift
unsigned int Xorshift() {
static unsigned int tx = 123456789, ty = 362436069, tz = 521288629, tw = 88675123;
unsigned int tt = (tx ^ (tx << 11));
tx = ty; ty = tz; tz = tw;
return (tw = (tw ^ (tw >> 19)) ^ (tt ^ (tt >> 8)));
}
template<class Rng>
class node_t {
public:
Rng val; //
node_t<Rng>* ch[2]; //
LL pri; //
LL cnt; //
Rng sum; //
static LL node_count; //
static const LL MAX_N = 4000000 + 10; //
void* operator new(std::size_t) {
static node_t<Rng> pool[MAX_N]; //
return pool + node_count++;
}
static void delete_all() {
node_count = 0;
}
node_t(Rng v) {
val = v;
ch[0] = ch[1] = NULL;
cnt = 1;
sum = v;
pri = Xorshift();
}
node_t() {
val = Rng();
ch[0] = ch[1] = NULL;
cnt = 1;
sum = val;
pri = Xorshift();
}
node_t<Rng>* update() {
node_t<Rng>* t = this;
t->cnt = (t->ch[0] ? t->ch[0]->cnt : 0) + (t->ch[1] ? t->ch[1]->cnt : 0) + 1;
if (t->ch[0])t->sum = t->ch[0]->sum + t->val;
else t->sum = t->val;
if (t->ch[1])t->sum = t->sum + t->ch[1]->sum;
return t;
}
};
template<class Rng>
LL node_t<Rng>::node_count = 0;
//2treap
template<class Rng>
node_t<Rng>* merge(node_t<Rng>* l, node_t<Rng>* r) {
if (!l || !r)return !l ? r : l;
if (l->pri > r->pri) {
l->ch[1] = merge(l->ch[1], r);
return l->update();
}
else {
r->ch[0] = merge(l, r->ch[0]);
return r->update();
}
}
//treap[0,k)[k,n)split
template<class Rng>
pair<node_t<Rng>*, node_t<Rng>*> split(node_t<Rng>* t, LL k) {
typedef pair<node_t<Rng>*, node_t<Rng>*> P;
if (!t)return P(NULL, NULL);
LL count = t->ch[0] ? t->ch[0]->cnt : 0;
if (k <= count) {
P s = split(t->ch[0], k);
t->ch[0] = s.second;
return P(s.first, t->update());
}
else {
P s = split(t->ch[1], k - count - 1);
t->ch[1] = s.first;
return P(t->update(), s.second);
}
}
//treap trkt
template<class Rng>
node_t<Rng>* insert(node_t<Rng>* tr, LL k, node_t<Rng>* t) {
auto sp = split(tr, k);
sp.first = merge(sp.first, t);
return merge(sp.first, sp.second);
}
//treap trk
template<class Rng>
node_t<Rng>* erase(node_t<Rng>* tr, LL k) {
auto sp = split(tr, k);
auto sp2 = split(sp.second, 1);
//delete sp2.first;
return merge(sp.first, sp2.second);
}
template<class Rng>
void print(node_t<Rng>* root) {
if (root == NULL)return;
print(root->ch[0]);
cout << " " << root->val;
print(root->ch[1]);
return;
}
template<class Rng>
node_t<Rng>* index(node_t<Rng>* root, LL n) {
if (!root)return NULL;
if (n >= root->cnt)return NULL;
LL ln = (root->ch[0] ? root->ch[0]->cnt : 0);
LL rn = (root->ch[1] ? root->ch[1]->cnt : 0);
if (n < ln)return index(root->ch[0], n);
else if (n == ln)return root;
else return index(root->ch[1], n - (ln + 1));
}
template<class Rng>
node_t<Rng>* change(node_t<Rng>* root, LL n, Rng x) {
if (!root)return NULL;
LL ln = (root->ch[0] ? root->ch[0]->cnt : 0);
LL rn = (root->ch[1] ? root->ch[1]->cnt : 0);
if (n >= ln + rn + 1)return NULL;
if (n < ln) {
node_t<Rng>* r = change(root->ch[0], n, x);
root->update();
return r;
}
else if (n == ln) {
root->val = x;
root->update();
return root;
}
else {
node_t<Rng>* r = change(root->ch[1], n - (ln + 1), x);
root->update();
return r;
}
}
//[l,r]
template<class Rng>
Rng rangesum(node_t<Rng>* root, LL l, LL r) {
if (root == NULL)return Rng();
LL ln = (root->ch[0] ? root->ch[0]->cnt : 0);
LL rn = (root->ch[1] ? root->ch[1]->cnt : 0);
if (r < 0 || l > ln + rn)return Rng();
l = max((LL)0, l);
r = min(ln + rn, r);
if (l == 0 && r == ln + rn)return root->sum;
Rng ans = rangesum(root->ch[0], l, r);
if (l <= ln && ln <= r)ans = ans + root->val;
ans = ans + rangesum(root->ch[1], l - ln - 1, r - ln - 1);
return ans;
}
int Q, K;
void solve() {
cin >> Q >> K;
node_t<T>* node = nullptr;
for (int q = 0; q < Q; q++) {
int type;
cin >> type;
if (type == 1) {
LL v;
cin >> v;
if (node == nullptr) {
node = new node_t<T>(T(v));
}
else {
int s = -1, e = node->cnt;
while (e - s > 1) {
int mid = (e + s) / 2;
if (index(node, mid)->val.v < v)s = mid;
else e = mid;
}
node = insert(node, e, new node_t<T>(T(v)));
}
}
else {
if (node == nullptr) {
cout << -1 << "\n";
}
else if (K > (node->cnt)) {
cout << -1 << "\n";
}
else {
auto elem = index(node, K - 1);
cout << elem->val.v << "\n";
node = erase(node, K - 1);
}
}
}
}
void naive() {
}
void outputinput() {
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0