bef-> NO.19

Veröffentlicht am

[ZJOI2005]午餐

题目描述

上午的训练结束了，THU ACM小组集体去吃午餐，他们一行N人来到了著名的十食堂。这里有两个打饭的窗口，每个窗口同一时刻只能给一个人打饭。由于每个人的口味（以及胃口）不同，所以他们要吃的菜各有不同，打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同，所以吃饭花费的时间也是可能有所不同的。

THU ACM小组的吃饭计划是这样的：先把所有的人分成两队，并安排好每队中各人的排列顺序，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口去排队打饭。每个人打完饭后立刻开始吃，所有人都吃完饭后立刻集合去六教地下室进行下午的训练。

现在给定了每个人的打饭时间和吃饭时间，要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。

假设THU ACM小组在时刻0到达十食堂，而且食堂里面没有其他吃饭的同学（只有打饭的师傅）。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响的，而且每个人打饭的时间是和窗口无关的，打完饭之后立刻就开始吃饭，中间没有延迟。

现在给定N个人各自的打饭时间和吃饭时间，要求输出最佳方案下所有人吃完饭的时刻。

输入输出格式

输入格式：

第一行一个整数N，代表总共有N个人。

以下N行，每行两个整数 Ai，Bi。依次代表第i个人的打饭时间和吃饭时间。

输出格式：

一个整数T，代表所有人吃完饭的最早时刻。

输入输出样例

输入样例#1：

1
2
3
4
5
6
5
2 2
7 7
1 3
6 4
8 5

输出样例#1：

1
17

说明

所有输入数据均为不超过200的正整数。

题解

一道贪心+dp的好题（然而我只会贪心qwq）

首先思考一下发现打饭时间不管怎么安排用的时间肯定是不变的，唯一有区别的是吃饭时间结束的早晚。

因此我们贪心的将吃饭时间多的放后面。

然后是dp，我居然看了数据范围没想出状态。。

设

表示前

个人在一食堂打

时间饭所用的最小时间。

我们只需要考虑第i个人在1号还是2号食堂。

然后对于一号食堂转移就是

max里的左边表示当前打饭+吃饭时间较短不会对下一人产生影响， 右边表示吃饭时间延续到下一人。

对于二号食堂同理。

这题的dp还是挺难想的。。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 205
struct Node
{
    int v , k;
}p[maxn];
inline bool operator < (Node x , Node y)
{
    // if(x.v == y.v) return x.v > y.v;
    return x.k > y.k ;
}
int ans , n , f[maxn][maxn*maxn] , s[maxn];
int main()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d%d",&p[i].v,&p[i].k);
    std::sort(p+1,p+n+1);
    for(int i = 1 ; i <= n ; ++i)
        s[i] = s[i-1] + p[i].v;
    // for(int i = 1 ; i <= n ; ++i)
    //     printf("%d %d\n",p[i].v,p[i].k);
    std::memset(f,0x7f,sizeof(f));
    f[0][0] = 0;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= s[i] ; ++j)
        {
            if(j >= p[i].v) f[i][j] = std::min(f[i][j] , std::max(f[i-1][j-p[i].v] , j + p[i].k));
            f[i][j] = std::min(f[i][j] , std::max(f[i-1][j], s[i] - j + p[i].k) );
        }
    int ans = 0x7ffffff ;
    for(int i = 1 ; i <= s[n] ; ++i)
        ans = std::min(ans , f[n][i]);
    printf("%d",ans);
}

[USACO08NOV]奶牛混合起来Mixed Up Cows

题目描述

Each of Farmer John’s N (4 <= N <= 16) cows has a unique serial number S_i (1 <= S_i <= 25,000). The cows are so proud of it that each one now wears her number in a gangsta manner engraved in large letters on a gold plate hung around her ample bovine neck.

Gangsta cows are rebellious and line up to be milked in an order called ‘Mixed Up’. A cow order is ‘Mixed Up’ if the sequence of serial numbers formed by their milking line is such that the serial numbers of every pair of consecutive cows in line differs by more than K (1 <= K <= 3400). For example, if N = 6 and K = 1 then 1, 3, 5, 2, 6, 4 is a ‘Mixed Up’ lineup but 1, 3, 6, 5, 2, 4 is not (since the consecutive numbers 5 and 6 differ by 1).

How many different ways can N cows be Mixed Up?

For your first 10 submissions, you will be provided with the results of running your program on a part of the actual test data.

POINTS: 200

约翰家有N头奶牛，第i头奶牛的编号是Si，每头奶牛的编号都是唯一的。这些奶牛最近 在闹脾气，为表达不满的情绪，她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队 伍中，相邻奶牛的编号之差均超过K。比如当K = 1时，1, 3, 5, 2, 6, 4就是一支混乱的队伍， 而1, 3, 6, 5, 2, 4不是，因为6和5只差1。请数一数，有多少种队形是混乱的呢？

输入输出格式

输入格式：

* Line 1: Two space-separated integers: N and K

* Lines 2..N+1: Line i+1 contains a single integer that is the serial number of cow i: S_i

输出格式：

* Line 1: A single integer that is the number of ways that N cows can be ‘Mixed Up’. The answer is guaranteed to fit in a 64 bit integer.

输入输出样例

输入样例#1：

1
2
3
4
5
4 1 
3 
4 
2 
1

输出样例#1：

1
2

说明

The 2 possible Mixed Up arrangements are:

3 1 4 2

2 4 1 3

题解

是一道状态压缩dp的简单题。

理清题意，我们只需要关注最后加进去的一头牛和没加之前有多少方案，最后加的这头牛可以是之前状态没加的任何一头牛，然后之前加的最后一头牛可以是状态中的任何一头牛。

我们设

表示状态为S且最后加入一头牛是i的方案数为多少

初始化对于只有一头牛我们都设成是一种方案（因为后面的状态从它转移当且仅当他们之间的编号>=k，因此不会多算）

然后枚举状态，枚举最后的牛，枚举新加入的牛，刷表转移。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 17
int S , p[maxn] , n , c;
long long f[maxn][1<<maxn] ;
int main()
{
    scanf("%d%d",&n,&c);
    for(int i = 0 ; i < n ; ++i)
        scanf("%d",&p[i]);
    for(int i = 0 ; i < n ; ++i)
        f[i][1<<i] = 1;
    S = (1<<n)-1;
    for(int i = 0 ; i <= S ; ++i)
        for(int j = 0 ; j < n ; ++j)//the last cow join in
            for(int k = 0 ; k < n ; ++k)
                if((1<<j)&i)
                {
                    if((1<<k)&i) continue;
                    if(abs(p[j]-p[k]) <= c) continue;
                    f[k][i|(1<<k)] += f[j][i];
                }
    long long ans = 0;
    for(int i = 0 ; i < n ; ++i)
        ans += f[i][S];
    printf("%lld",ans);
}

「一本通 4.1 例 2」数星星 Stars

原题来自：Ural 1028

天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。如果一个星星的左下方（包含正左和正下）有 kkk 颗星星，就说这颗星星是 kkk 级的。

stars1.png

例如，上图中星星 555 是 333 级的（1,2,41,2,41,2,4 在它左下），星星 2,42,42,4 是 111 级的。例图中有 111 个 000 级，222 个 111 级，111 个 222 级，111 个 333 级的星星。

给定星星的位置，输出各级星星的数目。

一句话题意 \ 给定 nnn 个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。

输入格式

第一行一个整数 NNN，表示星星的数目；
接下来 NNN 行给出每颗星星的坐标，坐标用两个整数 x,yx,yx,y 表示；
不会有星星重叠。星星按 yyy 坐标增序给出，yyy 坐标相同的按 xxx 坐标增序给出。

输出格式

NNN 行，每行一个整数，分别是 000 级，111 级，222 级，……，N−1N-1N−1 级的星星的数目。

样例

样例输入

1
2
3
4
5
6
5
1 1
5 1
7 1
3 3
5 5

样例输出

1
2
3
4
5
1
2
1
1
0

数据范围与提示

对于全部数据，

题解

树状数组经典题。

假设题目没有给你按这种顺序，才算有点难度，应考虑如何按顺序加入一维树状数组才能算出个数。

假设我们按x坐标建立树状数组，从左往右将点插入树状数组中。那么y坐标在插入顺序中必须升序。

因为y坐标大的包含所有x坐标小于这个点的点。有点类似于扫描线？

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
int x , y , bit[maxn] , n , ans[maxn], ly;
inline int lowbit(int x){return x & -x;}
inline int query(int x)
{
    int ans = 0;
    for(int i = x ; i ; i -= lowbit(i))
        ans += bit[i];
    return ans;
}
inline void update(int x)
{
    for(int i = x ; i <= 32005; i += lowbit(i))
        bit[i] += 1;
}
int main()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; ++i)
    {
        scanf("%d%d",&x,&y); ++x,++y;
        ++ans[query(x)];
        update(x);
    }
    for(int i = 0 ; i <= n-1 ; ++i)
        printf("%d\n",ans[i]);
}

选课

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？

输入输出格式

输入格式：

第一行有两个整数N,M用空格隔开。(1<=N<=300,1<=M<=300)

接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1<=ki<=N, 1<=si<=20）。

输出格式：

只有一行，选M门课程的最大得分。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
7  4
2  2
0  1
0  4
2  1
7  1
7  6
2  2

输出样例#1：

1
13

题解

树上背包。

思路大致是这样的，还是以子树为单位。

由题意可知，每个点被选则它到跟的路径上的所有点都必须选。

设

表示i子树选j个的最大值是多少。

恩，就这样。。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 305
#define maxm 305
int f[maxn][maxm] , n , head[maxn] , m , val[maxn] , cnt;
struct edge{
    int next , to;
}e[maxn*2];
void dfs(int x , int cnt , int fx)
{
    if(cnt == 0) return;
    for(int i = head[x] ; i ; i = e[i].next)
    {
        int v = e[i].to;
        if(v == fx) continue;
        for(int k = 0 ; k < cnt ; ++k)
            f[v][k] = f[x][k] + val[v];
        dfs(v , cnt - 1 , x);
        for(int k = 1 ; k <= cnt ; ++k)
            f[x][k] = std::max(f[x][k] , f[v][k-1]);
    }
}
inline void add(int x , int y)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    head[x] = cnt;
}
int main()
{
    scanf("%d%d",&n,&m);
    int x , y;
    for(int i = 1 ; i <= n; ++i)
        scanf("%d%d",&x,&y) , add(i,x) , add(x,i) , val[i] = y;//the i
    dfs(0,m,0);
    printf("%d\n",f[0][m]);
}

NOIp 2012 D2T3 疫情控制

题目描述

HH 国有 nn个城市，这 nn 个城市用n-1n−1条双向道路相互连通构成一棵树，11号城市是首都，也是树中的根节点。

HH国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。

现在，在 HH 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。

请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。

输入输出格式

输入格式：

第一行一个整数nn，表示城市个数。

接下来的 n-1 行，每行33个整数，u,v,w，每两个整数之间用一个空格隔开，表示从城市 u到城市v 有一条长为 w 的道路。数据保证输入的是一棵树，且根节点编号为 1。

接下来一行一个整数 m，表示军队个数。

接下来一行 m个整数，每两个整数之间用一个空格隔开，分别表示这 m 个军队所驻扎的城市的编号。

输出格式：

一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1−1。

输入输出样例

输入样例#1：

1
2
3
4
5
6
4 
1 2 1 
1 3 2 
3 4 3 
2 
2 2

输出样例#1：

1
3

说明

【输入输出样例说明】

第一支军队在 22 号点设立检查点，第二支军队从 22 号点移动到33 号点设立检查点，所需时间为 33 个小时。

【数据范围】

保证军队不会驻扎在首都。

对于 20%的数据，

对于 40%的数据，

对于 60%的数据，

对于 80%的数据，

对于 100%的数据，

NOIP 2012 提高组 第二天 第三题

题解

竟然想出了D2T3的正解。

这道题的本质是基于二分答案的贪心，显然答案满足可行性单调。

对于每次答案的判断，我们让每个军队尽量跳到子树根，不往下跳（贪心）。

然后假如有子树没有军队，需要跨根，那就将到子树节点还有剩余距离的大的去尽量跳，注意本子树始终保持被控制状态。

Code：（然而并不是我写的233）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;

#define LL long long
const int maxn = 5e4 + 7;
int h[maxn], cnt = 1, n, m, st[maxn], tot;
int dep[maxn], f[maxn], F[maxn][22], ds[maxn][22];
struct ndd {int v, nxt, w;} G[maxn << 1];
struct DATA {LL v; int id;} a[maxn], b[maxn];
bool vis[maxn]; int tt;

void ins(int u, int v, int w) {
    G[cnt] = (ndd) {v, h[u], w}; h[u] = cnt++;
}
void dfs(int x, int fa, int deep, int w) {
    dep[x] = deep; f[x] = fa; ds[x][0] = w; F[x][0] = fa;
    for (int i = 1; i <= 20 && F[F[x][i - 1]][i - 1]; ++i) {
        F[x][i] = F[F[x][i - 1]][i - 1];
        ds[x][i] = ds[F[x][i - 1]][i - 1] + ds[x][i - 1];
    }
    for (int i = h[x]; i; i = G[i].nxt) {
        int v = G[i].v; if(v == fa) continue;
        dfs(v, x, deep + 1, G[i].w);
    }
}
void put_tag(int x) {
    bool p = 1, q = 0;
    for (int i = h[x]; i; i = G[i].nxt) {
        int v = G[i].v; if(v == f[x]) continue;
        put_tag(v); p &= vis[v]; q = 1;
    } if(x != 1 && p && q) vis[x] = 1;
}
void init() {
    tot = tt = 0;
    memset(vis, 0, sizeof vis);
}
bool cmp(DATA a, DATA b) {
    return a.v < b.v;
}
bool check(int res) {
    init();
    for (int i = 1; i <= m; ++i) {
        int x = st[i], t = 0;
        for (int j = 20; j >= 0; --j) if(F[x][j] && t + ds[x][j] <= res) { t += ds[x][j]; x = F[x][j];}
        if(x != 1) vis[x] = 1;
        else {
            x = st[i]; a[++tot].v = res - t;
            for (int j = 20; j >= 0; --j) if(F[x][j] > 1) x = F[x][j];
            a[tot].id = x;
        }
    } put_tag(1);
    for (int i = h[1]; i; i = G[i].nxt) {
        int v = G[i].v; if(vis[v]) continue;
        b[++tt].v = G[i].w; b[tt].id = v; 
    }
    sort(a + 1, a + tot + 1, cmp);
    sort(b + 1, b + tt + 1, cmp); int j = 1;
    for (int i = 1; i <= tot; ++i) {
        if(!vis[a[i].id]) vis[a[i].id] = 1;
        else if(a[i].v >= b[j].v) vis[b[j].id] = 1;
        while(vis[b[j].id] && j <= tt) ++j;
    } return j > tt;
}

int main() {
    scanf("%d", &n); int res = 0;
    for (int i = 1; i <= n - 1; ++i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        ins(u, v, w); ins(v, u, w); res += w;
    } dfs(1, 0, 1, 0);
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) scanf("%d", &st[i]);
    int l = 0, r = res, ans = 0, ret = 0;
    for (int i = 1; i <= n; ++i) ret += (dep[i] == 2);
    if(m < ret) {puts("-1"); return 0;}
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(check(mid)) {ans = mid; r = mid - 1;}
        else l = mid + 1; 
    } printf("%d\n", ans);
    return 0;
}

[NOI2004]郁闷的出纳员

题目描述

OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。

工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。

老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。

好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？

如果某个员工的初始工资低于最低工资标准,那么将不计入最后的答案内

输入输出格式

输入格式：

第一行有两个非负整数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是一个正整数。

在初始时，可以认为公司里一个员工也没有。

输出格式：

输出文件的行数为F命令的条数加一。

对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。

输出文件的最后一行包含一个整数，为离开公司的员工的总数。

输入输出样例

输入样例#1：

复制

1
2
3
4
5
6
7
8
9
10
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2

输出样例#1：

复制

1
2
3
4
10
20
-1
2

说明

I命令的条数不超过100000

A命令和S命令的总条数不超过100

F命令的条数不超过100000

每次工资调整的调整量不超过1000

新员工的工资不超过100000

题解

和平衡树板子只差一个变量用来维护工资增量，这样就只需要让平衡树维护元素相对关系就可以了。

很失败的写了n个小时qwq。原因竟是没看题目最后一句话。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <ctime>
#define INF 0x7fffffff
int ans , x, n , minn;
struct Treap{
    #define maxn 100005
    #define INF 0x7fffffff
    #define ls(Node) ls[Node]
    #define rs(Node) rs[Node]//avoid write() to modify....
    #define v(Node) v[Node]
    #define p(Node) p[Node]
    #define sz(node) sz[node]
    #define cnt(node) cnt[node]
    // #define ll long long
    int ls[maxn] , rs[maxn] , v[maxn] , p[maxn] , cnt[maxn] , sz[maxn] , rt, tot , det;
    inline void upd(const int& k){sz[k] = sz[ls[k]] + sz[rs[k]] + cnt[k];}
    inline Treap(){
        srand(time(NULL));
    }
    inline int random(){return rand()%998244353 ;}
    inline void Zig(int &x)
    {
        int lson = ls[x];
        ls[x] = rs[lson];
        rs[lson] = x;
        sz[lson] = sz[x];
        upd(x);
        x = lson;//maintain the subtree root
    }
    inline void Zag(int &x)
    {
        int rson = rs[x];
        rs[x] = ls[rson];
        ls[rson] = x;
        sz[rson] = sz[x];
        upd(x);
        x = rson ;
    }
    void insert(int& Node , int vx)
    {
        if(!Node)
        {
            Node = ++tot;
            v[Node] = vx;
            p[Node] = random();
            cnt[Node] = sz[Node] = 1;
            ls[Node] = rs[Node] = 0;
            return ;
        }
        else ++sz[Node];
        if(v[Node] == vx) ++cnt[Node];
        else if(vx < v[Node])
        {
            insert(ls[Node] , vx);
            if(p[ls[Node]] < p[Node]) Zig(Node);
        }
        else
        {
            insert(rs[Node] , vx);
            if(p[rs[Node]] < p[Node]) Zag(Node);
        }
    }
    void Delete(int& Node , const int& vx)
    {
        if(!Node) return ; //the number does not exists in Treap
        if(v[Node] == vx)
        {
            if(cnt[Node] > 1) --cnt[Node] , --sz[Node];
            else if(!ls[Node] || !rs[Node]) Node = ls[Node] + rs[Node];
            //if above do not running , mean this Node haven't be a link node
            else if(p[ls[Node]] < p[rs[Node]]) Zig(Node) , Delete(Node , vx);
            else Zag(Node) , Delete(Node , vx);
            return ;
        }
        --sz[Node];
        if(v[Node] > vx) Delete(ls[Node] , vx);
        else Delete(rs[Node] , vx);
    }
    inline int QueryPre(const int& vx)
    {
        int Node = rt , res = -INF;
        while(Node)
        {
            if(v[Node] < vx) res = v[Node] , Node = rs[Node];
            else Node = ls[Node];
        }
        return res;
    }
    inline int QueryNext(const int& vx)
    {
        int Node = rt , ans = INF;
        while(Node)
        {
            if(v[Node] > vx) ans = v[Node] , Node = ls[Node];
            else Node = rs[Node];
        }
        return ans;
    }
    inline int kRank(int k)//from small to big
    {
        int Node = rt , ans = -1;
        while(Node)
        {
            if(sz[ls[Node]] < k && sz[ls[Node]] + cnt[Node] >= k) return v[Node] ;
            if(sz[ls[Node]] >= k)  Node = ls[Node] ;
            else k -= sz[ls[Node]] + cnt[Node] , Node = rs[Node];
        }
        return ans;
    }
    inline int kRankBig(int k)
    {
        int Node = rt , ans = INF;
        while(Node)
        {
            if(sz[rs[Node]] < k && sz[rs[Node]] + cnt[Node] >= k)   return v[Node];
            if(sz[rs[Node]] >= k)   Node = rs[Node];
            else k -= sz[rs[Node]] + cnt[Node] , Node = ls[Node];
        }
        return ans;
    }
    inline int getRank(const int& x)
    {
        int Node = rt , ans = 0;
        while(Node)
        {
            if(v[Node] == x)   { ans += sz[ls[Node]] + 1; return ans;}
            else if(v[Node] > x) Node = ls[Node];
            else ans += sz[ls[Node]] + cnt[Node] , Node = rs[Node];
        }
        return ans;
    }
    void Delete_kBelow(int& Node , int k)
    {
        if(!Node) return;
        if(v[Node] + det < k)
        {
            ans += sz[ls(Node)] + cnt[Node]; // they will be deleted
            Node = rs(Node);
            Delete_kBelow(Node,k);
            upd(Node);
        }
        else Delete_kBelow(ls(Node),k) , upd(Node);
    }
}tr;
int main()
{
    scanf("%d%d",&n,&minn);
    for(int i = 1 ; i <= n ; ++i)
    {
        char ch;
        std::cin>>ch;
        if(ch == 'I')
        {
            scanf("%d",&x);
            if(x < minn) continue;
            tr.insert(tr.rt,x - tr.det);
        }
        if(ch == 'A')  scanf("%d",&x) , tr.det += x;
        // if(ch == S')  scanf("%d",&x);
        if(ch == 'S')  scanf("%d",&x) , tr.det -= x , tr.Delete_kBelow(tr.rt,minn);
        if(ch == 'F')
        {
            scanf("%d",&x);
            int ans = tr.kRankBig(x);
            if(ans == INF) puts("-1");
            else printf("%d\n",ans+tr.det);
        }
    }
    printf("%d",ans);
}