记录编号	149448	评测结果	AAAAAAAAAA
题目名称	[HAOI 2008]排名系统	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.327 s
提交时间	2015-02-24 13:14:01	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
class Player{
public:
	string name;
	int score;
	int tim;
	Player(string n="",int s=0,int t=0){
		name=n;
		score=s;
		tim=t;
	}
};
class Compare{
public:
	bool operator ()(const Player &a,const Player &b)const{
		if(a.score>b.score) return true;
		if(a.score<b.score) return false;
		if(a.tim<b.tim) return true;
		if(a.tim>b.tim) return false;
		return a.name<b.name;
	}
};
cc_hash_table<string,Player> MP;
//typedef tree<Player,null_type,Compare,rb_tree_tag,tree_order_statistics_node_update> RB_Tree;
typedef tree<Player,null_mapped_type,Compare,rb_tree_tag,tree_order_statistics_node_update> RB_Tree;
RB_Tree T;
void work(void){
	int N;
	scanf("%d",&N);
	char buf[20];
	char s[20];
	int x;
	for(int i=1;i<=N;i++){
		scanf("%s",buf);
		if(buf[0]=='+'){//upload recod
			sscanf(&buf[1],"%s",s);
			scanf("%d",&x);
			cc_hash_table<string,Player>::point_iterator key=MP.find(s);
			if(key!=MP.end()) T.erase(key->second);
			Player P=Player(s,x,i);
			MP[s]=P;
			T.insert(P);
		}
		else if('0'<=buf[1]&&buf[1]<='9'){//query by order
			sscanf(&buf[1],"%d",&x);
			RB_Tree::iterator key=T.find_by_order(x-1);
			for(int i=1;i<=min(10,(int)MP.size()-x+1);i++){
				printf("%s ",key->name.c_str());
				key++;
			}
			printf("\n");
		}
		else{//query by name
			sscanf(&buf[1],"%s",s);
			printf("%d\n",T.order_of_key(MP[s])+1);
		}
	}
}
int main(){
	freopen("rank.in","r",stdin);
	freopen("rank.out","w",stdout);
	work();
	return 0;
}