记录编号	148377	评测结果	AAAAAAAAAA
题目名称	[NOI 2004]郁闷的出纳员	最终得分	100
用户昵称	rpCardinal	是否通过	通过
代码语言	C++	运行时间	0.402 s
提交时间	2015-02-11 13:32:20	内存使用	0.30 MiB

#include <cstdio>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<long long,null_mapped_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> TREE;

TREE T,T2;

int main()
{
    freopen("cashier.in","r",stdin);
    freopen("cashier.out","w",stdout);
    int n,mi,dt=0,ans=0,cnt=0; scanf("%d%d",&n,&mi);
    for (int i=1;i<=n;++i)
    {
        char c[10]; long long x,dis; int tmp; scanf("%s%lld",c,&x);
        switch (c[0])
        {
            case 'I': if (x>=mi) {x-=dt; T.insert((x<<20)+i); ++cnt;} break;
            case 'A': dt+=x; break;
            case 'S':
                dt-=x; dis=mi-dt; tmp=cnt-T.order_of_key(dis<<20);
                cnt-=tmp; ans+=tmp; T.split(dis<<20,T2); break;
            case 'F':
                if (x<=cnt) printf("%lld\n",((*T.find_by_order(x-1))>>20)+dt);
                else printf("-1\n");
        }
    }
    printf("%d\n",ans);
    fclose(stdin); fclose(stdout);
    return 0;
}