#607294 (C++17) No.649 ここでちょっとQK！

提出ソース

結果

問題	No.649 ここでちょっとQK！
ユーザー	f1b_maxbl00d
提出日時	2021-01-19 07:22:14
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	785 ms / 3,000 ms
コード長	6,525 bytes
コンパイル時間	3,729 ms
コンパイル使用メモリ	327,012 KB
実行使用メモリ	191,036 KB
最終ジャッジ日時	2024-05-09 08:26:51
合計ジャッジ時間	17,089 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	54 ms 190,992 KB
testcase_01	AC	55 ms 190,896 KB
testcase_02	AC	53 ms 190,840 KB
testcase_03	AC	23 ms 6,944 KB
testcase_04	AC	434 ms 190,844 KB
testcase_05	AC	415 ms 190,916 KB
testcase_06	AC	405 ms 191,036 KB
testcase_07	AC	54 ms 190,992 KB
testcase_08	AC	54 ms 190,860 KB
testcase_09	AC	55 ms 190,916 KB
testcase_10	AC	55 ms 190,852 KB
testcase_11	AC	55 ms 190,908 KB
testcase_12	AC	333 ms 190,920 KB
testcase_13	AC	340 ms 190,888 KB
testcase_14	AC	337 ms 190,936 KB
testcase_15	AC	343 ms 190,812 KB
testcase_16	AC	352 ms 190,904 KB
testcase_17	AC	396 ms 190,816 KB
testcase_18	AC	430 ms 190,828 KB
testcase_19	AC	444 ms 190,964 KB
testcase_20	AC	516 ms 190,872 KB
testcase_21	AC	562 ms 190,860 KB
testcase_22	AC	596 ms 190,808 KB
testcase_23	AC	643 ms 190,988 KB
testcase_24	AC	706 ms 190,812 KB
testcase_25	AC	755 ms 190,888 KB
testcase_26	AC	785 ms 190,848 KB
testcase_27	AC	55 ms 190,896 KB
testcase_28	AC	56 ms 190,964 KB
testcase_29	AC	54 ms 190,996 KB
testcase_30	AC	339 ms 190,888 KB
testcase_31	AC	341 ms 190,944 KB
testcase_32	AC	54 ms 190,824 KB
testcase_33	AC	54 ms 190,900 KB
testcase_34	AC	54 ms 190,936 KB
testcase_35	AC	2 ms 6,944 KB

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

ソースコード

raw source code

//#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;


//2つのtreapをマージ
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 trの場所kに要素tを追加
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 trの場所kの要素を消去
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() {
}

yukicoder

結果

テストケース

ソースコード