結果

問題 No.649 ここでちょっとQK！
ユーザー snrnsidysnrnsidy
提出日時 2021-05-12 02:50:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 469 ms / 3,000 ms
コード長 2,121 bytes
コンパイル時間 1,597 ms
コンパイル使用メモリ 145,864 KB
実行使用メモリ 51,252 KB
最終ジャッジ日時 2024-09-22 08:50:32
合計ジャッジ時間 8,783 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
7,344 KB
testcase_01 AC 4 ms
7,296 KB
testcase_02 AC 4 ms
7,312 KB
testcase_03 AC 30 ms
11,628 KB
testcase_04 AC 304 ms
50,252 KB
testcase_05 AC 303 ms
51,252 KB
testcase_06 AC 82 ms
16,756 KB
testcase_07 AC 4 ms
7,284 KB
testcase_08 AC 3 ms
7,204 KB
testcase_09 AC 4 ms
7,340 KB
testcase_10 AC 4 ms
7,172 KB
testcase_11 AC 4 ms
7,316 KB
testcase_12 AC 201 ms
27,636 KB
testcase_13 AC 200 ms
27,372 KB
testcase_14 AC 194 ms
27,708 KB
testcase_15 AC 197 ms
27,268 KB
testcase_16 AC 189 ms
28,404 KB
testcase_17 AC 218 ms
28,920 KB
testcase_18 AC 242 ms
30,464 KB
testcase_19 AC 264 ms
31,972 KB
testcase_20 AC 296 ms
38,384 KB
testcase_21 AC 308 ms
39,988 KB
testcase_22 AC 330 ms
41,348 KB
testcase_23 AC 372 ms
42,504 KB
testcase_24 AC 408 ms
43,596 KB
testcase_25 AC 419 ms
45,524 KB
testcase_26 AC 469 ms
47,800 KB
testcase_27 AC 4 ms
7,512 KB
testcase_28 AC 5 ms
7,484 KB
testcase_29 AC 5 ms
7,436 KB
testcase_30 AC 143 ms
22,236 KB
testcase_31 AC 142 ms
22,228 KB
testcase_32 AC 4 ms
7,376 KB
testcase_33 AC 4 ms
7,360 KB
testcase_34 AC 4 ms
7,368 KB
testcase_35 AC 4 ms
7,316 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