bzoj 3224 NOI2004郁闷的出纳员
2024-09-30 19:17:15
NOI2004郁闷的出纳员
2013年12月26日6,1818
输入描述 Input Description
第一行有两个非负整数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是一个正整数。
在初始时,可以认为公司里一个员工也没有。
输出描述 Output Description
输出文件的行数为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
题解:模板题吧,就是记录一个变化量搞一搞,裸的Treap,记录重复哪里搞错了,调了一个小时,无语了。
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio> #define ls tr[p].l
#define rs tr[p].r
#define N 100007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m,sz,rt,ans,bh;
char flag[];
struct Node
{
int l,r,val,siz,rnd,ct;//记录左儿子,右儿子,点值,该子树大小,随机的值,该点值出现的次数。
}tr[N];//最多多少个节点,就开多少空间 inline int rand(){
static int seed = ;
return seed = (int)((((seed ^ ) + 19260817ll) * 19890604ll) % );
}
inline void update(int p)
{
tr[p].siz=tr[ls].siz+tr[rs].siz+tr[p].ct;
}
void lturn(int &p)
{
int t=tr[p].r;tr[p].r=tr[t].l;tr[t].l=p;
tr[t].siz=tr[p].siz;update(p);p=t;
}
void rturn(int &p)
{
int t=tr[p].l;tr[p].l=tr[t].r;tr[t].r=p;
tr[t].siz=tr[p].siz;update(p);p=t;
}
void ins(int &p,int x)
{
if (p==)
{
p=++sz;
tr[p].siz=tr[p].ct=,tr[p].val=x,tr[p].rnd=rand();
return;
}
tr[p].siz++;
if (tr[p].val==x) tr[p].ct++;
else if (x>tr[p].val)
{
ins(tr[p].r,x);
if (tr[rs].rnd<tr[p].rnd) lturn(p);
}else
{
ins(tr[p].l,x);
if (tr[ls].rnd<tr[p].rnd) rturn(p);
}
}
int del(int &p,int x)
{
if (p==) return ;
if (tr[p].val<x)
{
int t=tr[ls].siz+tr[p].ct;p=rs;
return t+del(p,x);
}
else
{
int t=del(ls,x);tr[p].siz-=t;
return t;
}
}
int find_sz(int p,int x)
{
if (p==) return ;
if (x<=tr[ls].siz) return find_sz(ls,x);
x-=tr[ls].siz;
if (x<=tr[p].ct) return tr[p].val+bh;
x-=tr[p].ct;
return find_sz(rs,x);
}
int main()
{
n=read(),m=read();
for (int i=;i<=n;i++)
{
scanf("%s",flag);int x=read();
if (flag[]=='I'&&x>=m) ins(rt,x-bh);
if (flag[]=='A') bh+=x;
if (flag[]=='S')
{
bh-=x;
ans+=del(rt,m-bh);
}
if (flag[]=='F') printf("%d\n",(x>tr[rt].siz)?-:find_sz(rt,tr[rt].siz-x+));
}
printf("%d",ans);
}
最新文章
- zookeeper原理解析-选举
- 理解 Nova 架构 - 每天5分钟玩转 OpenStack(23)
- javascript学习6
- 边工作边刷题:70天一遍leetcode: day 86
- Solr常用查询语法笔记
- linux下的g++编译器安装
- 生产库MySQL配置文件my.cnf详解
- hadoop中的分布式缓存——DistributedCache
- escape,encodeURI,encodeURIComponent函数比较
- j2ee常用包的作用
- headfirst设计模式(6)—单例模式
- 1120 机器人走方格 V3(组合数)
- HBase指定大量列集合的场景下并发拉取数据时卡住的问题排查
- Java中Optional类的使用
- ActiveMQ消息的发送原理
- 07、RDD持久化
- jQuery获取对象简单实现方法
- openlayers3入门教程
- 6 Easy Steps to Learn Naive Bayes Algorithm (with code in Python)
- SAFEARRAY