| 记录编号 |
192407 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[HAOI 2008]排名系统 |
最终得分 |
100 |
| 用户昵称 |
 yyy |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
2.476 s |
| 提交时间 |
2015-10-10 20:55:35 |
内存使用 |
38.46 MiB |
显示代码纯文本
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <time.h>
using std::string;
typedef long long Long;
std::map<string,int> node;
namespace output
{
struct node
{
string s;
int n;
Long val;
node(string ss,int nn,Long vval)
{
s = ss;
n = nn;
val = vval;
}
node()
{}
bool operator<(const node & b)const
{
if(val == b.val)
return n < b.n;
return val < b.val;
}
};
std::vector<node> vec;
void output()
{
std::sort(vec.begin(),vec.end());
for(int i = 0;i < vec.size();i++)
{
if(i == 0)
printf("%s",vec[i].s.c_str());
else printf(" %s",vec[i].s.c_str());
}
printf("\n");
}
}
const int N = 500000;
namespace splay
{
struct Int
{
Long val;
int time;
bool operator < (const Int & b)const
{
if(val == b.val)
return time < b.time;
return val < b.val;
}
bool operator > (const Int & b)const
{
if(val == b.val)
return time > b.time;
return val > b.val;
}
bool operator == (const Int & b)const
{
return val == b.val && time == b.time;
}
bool operator != (const Int & b)const
{
return val != b.val || time != b.time;
}
Int(Long a,int b)
{
val = a;
time = b;
}
Int()
{}
};
struct node
{
string name;
Int val;
int son[2];
int size;
int is_right;
int father;
bool lazy;
};
int tot = 0;
node nodes[2 * N + 100];
#define LC(a) nodes[a].son[0]
#define RC(a) nodes[a].son[1]
#define SIZE(a) nodes[a].size
#define VAL(a) nodes[a].val
#define TIME(a) hash::time_in[nodes[a].name]
#define FATHER_ME(a) nodes[nodes[a].father].son[nodes[a].is_right]
int root = 0;
string now_name;
int newnode(Long val,int ti)
{
tot++;
nodes[tot].name = now_name;
nodes[tot].val = Int(val,ti);
nodes[tot].size = 1;
return tot;
}
void updata(int d)
{
if(!d)
return;
if(nodes[d].lazy)
SIZE(d) = SIZE(LC(d)) + SIZE(RC(d));
else SIZE(d) = SIZE(LC(d)) + SIZE(RC(d)) + 1;
}
void add(int & d,Long val,int is_right,const int & ti,const int & fat = 0)
{
if(!d)
{
d = newnode(val,ti);
nodes[d].is_right = is_right;
nodes[d].father = fat;
return;
}
if(Int(val,ti) > VAL(d))
add(RC(d),val,1,ti,d);
else add(LC(d),val,0,ti,d);
updata(d);
}
void r_r(int f)
{
if(!f)
return;
int s = nodes[f].son[0];
int b = nodes[s].son[1];
if(f == root)
root = s;
else FATHER_ME(f) = s;
nodes[s].is_right = nodes[f].is_right;
nodes[s].father = nodes[f].father;
nodes[f].father = s;
nodes[f].is_right = 1;
nodes[s].son[1] = f;
nodes[b].father = f;
nodes[b].is_right = 0;
nodes[f].son[0] = b;
updata(f);
updata(s);
}
void l_r(int f)
{
if(!f)
return;
int s = nodes[f].son[1];
int b = nodes[s].son[0];
if(f == root)
root = s;
else FATHER_ME(f) = s;
nodes[s].is_right = nodes[f].is_right;
nodes[s].father = nodes[f].father;
nodes[f].father = s;
nodes[f].is_right = 0;
nodes[s].son[0] = f;
nodes[b].father = f;
nodes[b].is_right = 1;
nodes[f].son[1] = b;
updata(f);
updata(s);
}
void del(int d)
{
if(!d)
return;
nodes[d].lazy = true;
updata(d);
int f = nodes[d].father;
while(f)
{
updata(f);
f = nodes[f].father;
}
}
int find_kth(int d,int k,int f = 0)
{
if(!d)
return 0;
if(nodes[d].lazy)
{
if(k <= SIZE(LC(d)))
return find_kth(LC(d),k);
return find_kth(RC(d),k - SIZE(LC(d)),d);
}
if(SIZE(LC(d)) == k - 1)
return d;
if(k <= SIZE(LC(d)))
return find_kth(LC(d),k);
return find_kth(RC(d),k - SIZE(LC(d)) - 1);
}
int find_num(int d,Long val,int ti)
{
if(!d)
return 0;
int sz = 0;
Int v = Int(val,ti);
while(nodes[d].val != v)
{
if(v > nodes[d].val)
{
sz += SIZE(LC(d)) + 1;
if(nodes[d].lazy)
sz--;
d = RC(d);
}
else d = LC(d);
}
sz += SIZE(LC(d)) + 1;
if(nodes[d].lazy)
sz--;
return sz;
}
void rot(int a)
{
if(!a)
return;
if(nodes[a].is_right)
l_r(nodes[a].father);
else r_r(nodes[a].father);
}
void splay(int a)
{
if(!a)
return;
while(a != root)
{
if(nodes[a].is_right != nodes[nodes[a].father].is_right)
{
rot(a);
rot(a);
}
else
{
rot(nodes[a].father);
rot(a);
}
}
}
};
char str[20];
int main()
{
{
int _q=10<<20;
char *_p=(char*)malloc(_q)+_q;
__asm__("movl %0, %%esp\n"::"r"(_p));
}
freopen("rank.in","r",stdin);
freopen("rank.out","w",stdout);
int n = 0;
scanf("%d",&n);
char c = 0;
int op = 0;
int num = 0;
int re = 0;
int m = 0;
Long Lnum = 0LL;
int tt = 0;
string nm;
for(int i = 0;i < n;i++)
{
do
{
c = getchar();
}
while(c == ' ' || c == '\n' || c == '\t');
if(c == '?')
{
c = getchar();
if(c >= '0' && c <= '9')
op = 1;//给定排名问名字
else op = 2;//给定名字问排名
ungetc(c,stdin);
}
else op = 3;//改分数
if(op == 1)
{
scanf("%d",&num);
//continue;
output::vec.clear();
re = 0;
for(int p = num;p < num + 10;p++)
{
if(p > splay::nodes[splay::root].size)
break;
if(re == 0)
re = splay::find_kth(splay::root,p);
else re = splay::find_kth(splay::nodes[re].son[1],1);
splay::splay(re);
output::vec.push_back(output::node(splay::nodes[re].name,splay::nodes[re].val.time,splay::nodes[re].val.val));
}
output::output();
}
else if(op == 2)
{
scanf("%s",str);
//continue;
int hh = node[string(str)];
splay::splay(hh);
Lnum = splay::nodes[hh].val.val;
tt = splay::nodes[hh].val.time;
printf("%d\n",splay::find_num(splay::root,Lnum,tt));
}
else
{
scanf("%s",str);
std::cin>>Lnum;
Lnum = -Lnum;
nm = str;
m = node[nm];
splay::del(m);
if(m)
splay::splay(m);
splay::now_name = nm;
splay::add(splay::root,Lnum,0,i + 1);
node[nm] = splay::tot;
splay::splay(splay::tot);
}
//if(i % 100000 == 0)
// fprintf(stderr,"%d %d %d\n",i,clock(),op);
}
return 0;
}