結果

問題 No.649 ここでちょっとQK！
ユーザー snrnsidysnrnsidy
提出日時 2021-05-12 02:50:45
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 501 ms / 3,000 ms
コード長 2,121 bytes
コンパイル時間 1,723 ms
コンパイル使用メモリ 146,216 KB
実行使用メモリ 50,360 KB
最終ジャッジ日時 2023-10-22 07:46:13
合計ジャッジ時間 9,854 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
7,324 KB
testcase_01 AC 4 ms
7,324 KB
testcase_02 AC 4 ms
7,324 KB
testcase_03 AC 29 ms
11,940 KB
testcase_04 AC 306 ms
50,360 KB
testcase_05 AC 303 ms
50,360 KB
testcase_06 AC 82 ms
15,964 KB
testcase_07 AC 4 ms
7,324 KB
testcase_08 AC 4 ms
7,324 KB
testcase_09 AC 4 ms
7,324 KB
testcase_10 AC 4 ms
7,324 KB
testcase_11 AC 4 ms
7,324 KB
testcase_12 AC 207 ms
27,576 KB
testcase_13 AC 210 ms
27,576 KB
testcase_14 AC 203 ms
27,564 KB
testcase_15 AC 204 ms
27,576 KB
testcase_16 AC 202 ms
27,576 KB
testcase_17 AC 232 ms
29,164 KB
testcase_18 AC 260 ms
30,476 KB
testcase_19 AC 286 ms
32,056 KB
testcase_20 AC 308 ms
37,664 KB
testcase_21 AC 326 ms
39,244 KB
testcase_22 AC 357 ms
40,828 KB
testcase_23 AC 381 ms
42,412 KB
testcase_24 AC 432 ms
44,000 KB
testcase_25 AC 462 ms
45,580 KB
testcase_26 AC 501 ms
47,160 KB
testcase_27 AC 4 ms
7,324 KB
testcase_28 AC 4 ms
7,324 KB
testcase_29 AC 5 ms
7,324 KB
testcase_30 AC 160 ms
22,152 KB
testcase_31 AC 153 ms
22,144 KB
testcase_32 AC 4 ms
7,324 KB
testcase_33 AC 4 ms
7,324 KB
testcase_34 AC 4 ms
7,324 KB
testcase_35 AC 4 ms
7,324 KB
権限があれば一括ダウンロードができます

ソースコード

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