Bear and Displayed Friends题解

题目

Bear and Displayed Friends

描述

利马克是一只小北极熊。他喜欢通过社交网络与其他熊联系。他有n个朋友，他与其中第i个朋友的关系由一个独特的整数ti来描述。这个值越大，友谊就越好。没有两个朋友有相同的值ti。

春天开始了，熊的冬季睡眠结束了。利马克刚刚醒来并登录了。他所有的朋友都还在睡觉，因此他们都不在线。在接下来的几个小时里，他们中的一些（也许是全部）会出现在网上，一次一个。

系统显示正在在线的朋友。在屏幕上，最多可以显示k个朋友。如果有超过k个朋友在线，那么系统只显示其中最好的k个朋友–那些有最大蒂的朋友。

你的任务是处理两种类型的查询。

“1 id”–朋友id成为在线。保证他以前不在线。
“2 id”- 检查系统是否显示了朋友的ID。在另一行打印 “YES “或 “NO”。
你能帮助Limak并回答所有第二类的询问吗？

输入

第一行包含三个整数n、k和q（1≤n,q≤150000,1≤k≤min(6,n)）–分别是朋友的数量、显示的最大在线朋友数量和查询的数量。

第二行包含n个整数t1,t2,…,tn（1≤ti≤1e9），其中ti描述Limak与第i个朋友的关系有多好。

下面q行中的第i行包含两个整数typei和idi（1≤typei≤2,1≤idi≤n）–第i个查询。如果typei=1，那么朋友idi成为在线。如果typei=2，那么你应该检查一个朋友idi是否被显示。

保证没有两个第一类型的查询会有相同的白痴，因为一个朋友不可能在线两次。另外，保证至少有一个查询是第二种类型的（typei=2），所以输出不会是空的。

输出

对于每个第二类型的查询，如果给定的朋友被显示，则打印一行答案–”YES”（不带引号），否则打印 “NO”（不带引号）。

样例

输入

4 2 8
300 950 500 200
1 3
2 4
2 3
1 1
1 2
2 1
2 2
2 3

输出

NO
YES
NO
YES
YES

输入

6 3 9
50 20 51 17 99 24
1 3
1 4
1 5
1 2
2 4
2 2
1 1
2 4
2 3

输出

NO
YES
NO
YES

提示

在第一个例子中，Limak有4个朋友，他们最初都在睡觉。起初，系统显示无人，因为没有人在线。有以下8个查询。
“1 3”- 朋友3成为在线。
“2 4”–我们应该检查朋友4是否被显示。他甚至不在线，因此我们打印 “NO”。
“2 3”- 我们应该检查朋友3是否被显示。现在他是唯一在线的朋友，系统显示他。我们应该打印 “YES”。
“1 1”- 朋友1变得在线。系统现在同时显示朋友1和朋友3。
“1 2”–朋友2变成在线。现在有3个朋友在线，但我们得到的是k=2，所以只能显示两个朋友。利马克与朋友1的关系比与其他两个在线朋友的关系差（t1<t2,t3），所以朋友1不会被显示。
“2 1”- 打印 “NO”。
“2 2”–打印 “YES”。
“2 3”–打印 “YES”。

补充

时间限制 2 秒
内存限制 256 MB
来源 FYOJ

题解

很适合联系优先队列的一道题……
直接打！

#include <bits/stdc++.h>
using namespace std;
int n,k,q;
int a[150010];
priority_queue <int,vector<int>,less<int> > q1,q2;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin >> n >> k >> q;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for (int i = 1; i <= q; i++){
		int ch,id;
		cin >> ch >> id;
		if (ch == 1){
			q1.push(a[id]);
		} else {
			if (!q1.empty()){
				q2 = q1;
				bool b = 0;
				for (int j = 1; j <= k; j++){
					if (a[id] == q2.top()){
						cout << "YES\n";
						b = 1;
						break;
					}
					q2.pop();
				}
				if (!b){
					cout << "NO\n";
				}
			} else {
				cout << "NO\n";
			}
		}
	}
	return 0;
}

测评结果 通过
分数 100
时间 0 MS
内存 720 KB
语言 C++
代码长度 700