結果

問題 No.649 ここでちょっとQK！
ユーザー snrnsidysnrnsidy
提出日時 2021-05-12 02:50:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 528 ms / 3,000 ms
コード長 2,121 bytes
コンパイル時間 1,803 ms
コンパイル使用メモリ 139,176 KB
最終ジャッジ日時 2025-01-21 10:12:50
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional> 
#include <iomanip>
#include <unordered_map>
#include <memory.h>
#include <cstring>
#include <fstream>
#include <assert.h>

using namespace std;

vector <long long int> tree;

void update(int node, int start, int end, int idx, int diff)
{
	if (idx < start || idx > end)
	{
		return;
	}
	tree[node] += diff;
	if (start != end)
	{
		int mid = (start + end) / 2;
		update(2 * node, start, mid, idx, diff);
		update(2 * node + 1, mid + 1, end, idx, diff);
	}
}

int findidx(int node, int start, int end, int k)
{
	if (start == end)
	{
		return start;
	}

	int mid = (start + end) / 2;

	if (tree[2 * node] >= k)
	{
		return findidx(2 * node, start, mid, k);
	}
	else
	{
		k -= tree[2 * node];
		return findidx(2 * node + 1, mid + 1, end, k);
	}
}

map <long long int, int> mapping;
map <int, long long int> inverse_mapping;
set <long long int> S;
vector<pair<int, long long int>> query;
int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, k,a, b;
	int h = ceil(log2(200010));
	int tree_size = (1 << (h + 1));
	tree.resize(tree_size);

	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		cin >> a;
		if (a == 1)
		{
			long long int b;
			cin >> b;
			query.push_back(make_pair(a, b));
			S.insert(b);
		}
		else
		{
			query.push_back(make_pair(a, 0));
		}
	}
	int num = 0;
	for (auto it : S)
	{
		mapping[it] = num;
		inverse_mapping[num++] = it;
	}
	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		a = query[i].first;
		if (a == 1)
		{
			int b = mapping[query[i].second];
			query.push_back(make_pair(a, b));
			update(1, 0, 200010 - 1, b, 1);
			cnt++;
		}
		else
		{
			if (cnt < k)
			{
				cout << -1 << '\n';
				continue;
			}
			int idx = findidx(1, 0, 200010 - 1, k);
			cout << inverse_mapping[idx] << '\n';
			update(1, 0, 200010 - 1, idx, -1);
			cnt--;
		}
	}

	return 0;
}
0