- Time Limit: 5 Sec Memory Limit: 64 MB
- Submit: 13723 Solved: 4989
- [Submit][Status][Discuss https://www.lydsy.com/JudgeOnline/bbs.PHP?id=1503 ]
- Description
OIER 公司是一家大型专业化软件公司, 有着数以万计的员工. 作为一名出纳员, 我的任务之一便是统计每位员工的
工资. 这本来是一份不错的工作, 但是令人郁闷的是, 我们的老板反复无常, 经常调整员工的工资. 如果他心情好
, 就可能把每位员工的工资加上一个相同的量. 反之, 如果心情不好, 就可能把他们的工资扣除一个相同的量. 我
真不知道除了调工资他还做什么其它事情. 工资的频繁调整很让员工反感, 尤其是集体扣除工资的时候, 一旦某位
员工发现自己的工资已经低于了合同规定的工资下界, 他就会立刻气愤地离开公司, 并且再也不会回来了. 每位员
工的工资下界都是统一规定的. 每当一个人离开公司, 我就要从电脑中把他的工资档案删去, 同样, 每当公司招聘
了一位新员工, 我就得为他新建一个工资档案. 老板经常到我这边来询问工资情况, 他并不问具体某位员工的工资
情况, 而是问现在工资第 k 多的员工拿多少工资. 每当这时, 我就不得不对数万个员工进行一次漫长的排序, 然后
告诉他答案. 好了, 现在你已经对我的工作了解不少了. 正如你猜的那样, 我想请你编一个工资统计程序. 怎么样
, 不是很困难吧?
Input
第一行有两个非负整数 n 和 min.n 表示下面有多少条命令, min 表示工资下界.
接下来的 n 行, 每行表示一条命令. 命令可以是以下四种之一:
名称 格式 作用
I 命令 I_k 新建一个工资档案, 初始工资为 k.
如果某员工的初始工资低于工资下界, 他将立刻离开公司.
A 命令 A_k 把每位员工的工资加上 k
S 命令 S_k 把每位员工的工资扣除 k
F 命令 F_k 查询第 k 多的工资
_(下划线) 表示一个空格, I 命令, A 命令, S 命令中的 k 是一个非负整数, F 命令中的 k 是一个正整数.
在初始时, 可以认为公司里一个员工也没有.
I 命令的条数不超过 100000
A 命令和 S 命令的总条数不超过 100
F 命令的条数不超过 100000
每次工资调整的调整量不超过 1000
新员工的工资不超过 100000
Output
输出行数为 F 命令的条数加一.
对于每条 F 命令, 你的程序要输出一行, 仅包含一个整数, 为当前工资第 k 多的员工所拿的工资数,
如果 k 大于目前员工的数目, 则输出 - 1.
输出文件的最后一行包含一个整数, 为离开公司的员工的总数.
- Sample Input
- 9 10
- I 60
- I 70
- S 50
- F 2
- I 30
- S 15
- A 5
- F 1
- F 2
- Sample Output
- 10
- 20
- -1
- 2
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- using namespace std;
- struct Treap
- {
- int left,right,val,rnd,size;
- }tree[100005];
- int n,m,size,root,ans,delta;
- void update(int k)
- {
- tree[k].size=tree[tree[k].left].size+tree[tree[k].right].size+1;
- }
- void lturn(int &k)
- {
- int t=tree[k].right;
- tree[k].right=tree[t].left;
- tree[t].left=k;
- tree[t].size=tree[k].size;
- update(k);
- k=t;
- }
- void rturn(int &k)
- {
- int t=tree[k].left;
- tree[k].left=tree[t].right;
- tree[t].right=k;
- tree[t].size=tree[k].size;
- update(k);
- k=t;
- }
- void insert(int &k,int x)
- {
- if(k==0)
- {
- size++;k=size;
- tree[k].size=1;
- tree[k].val=x;
- tree[k].rnd=rand();
- return;
- }
- tree[k].size++;
- if(x>tree[k].val)
- {
- insert(tree[k].right,x);
- if(tree[tree[k].right].rnd<tree[k].rnd) lturn(k);
- }
- else
- {
- insert(tree[k].left,x);
- if(tree[tree[k].left].rnd<tree[k].rnd) rturn(k);
- }
- }
- int del(int &k,int x)
- {
- int t;
- if(k==0) return 0;
- if(tree[k].val<x)
- {
- t=tree[tree[k].left].size+1;
- k=tree[k].right;
- return t+del(k,x);
- }
- else
- {
- t=del(tree[k].left,x);
- tree[k].size-=t;
- return t;
- }
- }
- int query(int k,int x)
- {
- if(tree[tree[k].left].size+1==x) return tree[k].val+delta;
- else if(tree[tree[k].left].size+1<x) return query(tree[k].right,x-tree[tree[k].left].size-1);
- else return query(tree[k].left,x);
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- while(n--)
- {
- char ch[5];
- int x;
- scanf("%s %d",ch,&x);
- switch(ch[0])
- {
- case 'I':if(x>=m)insert(root,x-delta);break;
- case 'A':delta+=x;break;
- case 'S':delta-=x;ans+=del(root,m-delta);break;
- case 'F':
- if(tree[root].size>=x) printf("%d\n",query(root,tree[root].size-x+1));
- else printf("-1\n");
- break;
- }
- }
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2794405.html