結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー akusyounin2412
提出日時 2018-07-20 15:56:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 512 ms / 3,000 ms
コード長 7,795 bytes
コンパイル時間 1,600 ms
コンパイル使用メモリ 136,696 KB
実行使用メモリ 19,200 KB
最終ジャッジ日時 2024-12-26 04:22:32
合計ジャッジ時間 10,938 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include<time.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>
//#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
long long MOD = 1000000000+7;
constexpr long long INF = numeric_limits<LL>::max();
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Mfor(i,mf) for(LL i=mf-1;i>=0;i--)
LL h, w, n, m, k, t, s, q, last, cnt, sum[2000000], ans, d[200000], a[2000000], b[2000000];
string str,ss;
int f[26][26];
char c;
int di[4][2] = { { 0,1 },{ 1,0 },{ -1,0 } ,{ 0,-1 } };
struct Edge { LL to, cost; };
vector<LL>vec[26];
vector<Pll>v;
map<string, LL>ma;
set<LL>st;
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}
//
// a[0],a[1],a[2],...,a[k],...
//
template <typename T>
struct node_t {
	T val;         // 値
	node_t *lch;
	node_t *rch;
	double  pri;   // 優先度
	int     cnt;   // 部分木のサイズ
	T       min_val;
	T       lazy_val;
	bool    lazy;
	node_t(T v, double p) : val(v), lch(nullptr), rch(nullptr),
		pri(p), cnt(1), min_val(v),
		lazy_val(0), lazy(false) {}
	~node_t() {
		delete lch;
		delete rch;
	}
	static void push(node_t *t) {
		if (!t)
			return;
		if (t->lazy)
		{
			t->val += t->lazy_val;
			t->min_val += t->lazy_val;
			if (t->lch)
			{
				t->lch->lazy = true;
				t->lch->lazy_val += t->lazy_val;
			}
			if (t->rch)
			{
				t->rch->lazy = true;
				t->rch->lazy_val += t->lazy_val;
			}
			t->lazy_val = 0;
			t->lazy = false;
		}
	}
	static int count(node_t *t) { return t ? t->cnt : 0; }
	static int Min(node_t *t) { return t ? t->min_val : std::numeric_limits<T>::max(); }
	static node_t *update(node_t *t) {
		assert(t != nullptr);
		push(t);
		t->cnt = count(t->lch) + count(t->rch) + 1;
		push(t->lch);
		push(t->rch);
		t->min_val = std::min({ (T)Min(t->lch), (T)Min(t->rch), t->val });
		return t;
	}
	static node_t *merge(node_t *l, node_t *r) {
		if (!l || !r)
			return (!l) ? r : l;
		update(l);
		update(r);
		if (l->pri > r->pri)
		{
			l->rch = merge(l->rch, r);
			return update(l);
		}
		else
		{
			r->lch = merge(l, r->lch);
			return update(r);
		}
		assert(false);
		return nullptr;
	}
	//
	// node をたどることになる。k番目のノードで再帰が止まる
	//    [0,1,2,...,k-1,k,...]
	// -> [0,1,2,...,k-1] [k,...]
	//
	static std::pair<node_t*, node_t*> split(node_t* t, int k) {
		if (!t)
			return std::make_pair(nullptr, nullptr);
		update(t);
		if (k <= count(t->lch))
		{
			auto s = split(t->lch, k);
			t->lch = s.second;
			return std::make_pair(s.first, update(t));
		}
		else
		{
			auto s = split(t->rch, k - count(t->lch) - 1);
			t->rch = s.first;
			return std::make_pair(update(t), s.second);
		}
		assert(false);
		return std::make_pair(nullptr, nullptr);
	}
	static node_t *insert(node_t *t, int k, node_t *new_t) {
		auto s = split(t, k);
		return merge(merge(s.first, new_t), s.second);
	}
	static std::pair<node_t*, node_t*> erase(node_t *t, int k) {
		auto sr = split(t, k + 1);
		auto sl = split(sr.first, k);
		return std::make_pair(merge(sl.first, sr.second), sl.second);
	}
	static node_t *find(node_t *t, int k) {
		assert(t != nullptr);
		int c = count(t->lch);
		if (k == c)
			return t;
		if (k < c)
			return find(t->lch, k);
		return find(t->rch, k - c - 1);
	}
	static void traverse(node_t *t, const std::function<void(node_t *t)> &func) {
		if (!t)
			return;
		if (t->lch)
			traverse(t->lch, func);
		if (t->rch)
			traverse(t->rch, func);
		func(t);
		return;
	}
};
static int seed = 28313234; // seed はテキトー。デバッグしやすいように固定。
template <typename T>
struct Treap {
	typedef node_t<T> node;
	std::function<double(void)> dice_;
public:
	node * root_;
	Treap() : root_(nullptr) {
		dice_ = std::bind(std::uniform_real_distribution<double>(0.000,1.000), std::mt19937(seed));
	}
	~Treap() {}
	void insert(int k, T val) {
		root_ = node::insert(root_, k, new node(val, dice_()));
	}
	// value based
	int upper_bound(T val) {
		std::function<int(node*, int)> F = [&](node *s, int left)->int {
			assert(s != nullptr);
			if (val < s->val)
			{
				if (!s->lch)
					return left;
				else
					return F(s->lch, left);
			}
			else
			{
				int c = node::count(s->lch);
				if (!s->rch)
					return (left + (c + 1));
				else
					return F(s->rch, left + c + 1);
			}
		};
		if (!root_)
			return 0;
		return F(root_, 0);
	}
	void insert(T val) {
		insert(upper_bound(val), val);
	}
	void erase(int k) {
		node *p;
		std::tie(root_, p) = node::erase(root_, k);
		p->lch = p->rch = nullptr;
		delete p;
	}
	T find(int k) {
		if (!(0 <= k && k < node::count(root_)))return -1;
		node *p = node::find(root_, k);
		return p->val;
	}
	// shift for [l,r) 区間ないの要素を一つずらす。
	void shift(int l, int r) {
		if (l == r - 1) return;
		assert(l<r);
		auto sr = node::split(root_, r);
		auto sl = node::split(sr.first, l);
		auto lr = node::split(sl.second, r - l - 1);
		root_ = node::merge(node::merge(sl.first,
			node::merge(lr.second, lr.first)),
			sr.second);
	}
	int size() const { return node::count(root_); }
	// add to [l,r)
	void add(int l, int r, T val) {
		assert(l<r);
		auto sr = node::split(root_, r);
		auto sl = node::split(sr.first, l);
		auto lr = sl.second;
		lr->lazy = true;
		lr->lazy_val = val;
		root_ = node::merge(node::merge(sl.first, lr), sr.second);
	}
	// min at [l,r)
	T Min(int l, int r) {
		assert(l<r);
		auto sr = node::split(root_, r);
		auto sl = node::split(sr.first, l);
		auto lr = sl.second;
		T val = node::min(lr);
		// 戻す
		root_ = node::merge(node::merge(sl.first, lr), sr.second);
		return val;
	}
	T at(int k) {
		assert(0 <= k && k < size());
		auto sr = node::split(root_, k + 1);
		auto sl = node::split(sr.first, k);
		auto lr = sl.second;
		assert(lr != nullptr);
		T val = lr->val;
		root_ = node::merge(node::merge(sl.first, lr), sr.second);
		return val;
	}
	T get(int k) {
		if (0 <= k && k < size())
			return at(k);
		return 0;
	}
	void set(int k, T val) {
		auto sr = node::split(root_, k + 1);
		auto sl = node::split(sr.first, k);
		auto lr = sl.second;
		assert(lr != nullptr);
		lr->val = val;
		root_ = node::merge(node::merge(sl.first, lr), sr.second);
	}
	void _dump(node *t, std::string tab) {
		if (!t)
			return;
		std::cerr << tab << " " << t->val << " " << t->cnt << std::endl;
		if (t->lch)
		{
			_dump(t->lch, tab + "L");
		}
		if (t->rch)
		{
			_dump(t->rch, tab + "R");
		}
	}
	void dump() {
		std::cerr << "*******" << std::endl;
		_dump(root_, "");
		std::cerr << std::endl;
	}
};
Treap<LL>tr;
int main() {
	cin >> n >> m;
	rep(i, n) {
		LL x, y;
		cin >> x;
		if (x == 1) {
			cin >> y;
			tr.insert(y);
		}
		else { 
			ans = tr.find(m - 1);
			cout <<ans<< endl;
			if(ans!=-1)
			tr.erase(m - 1);
		}
	}
   return 0;
}
0