Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

出處 ：

/**********************************************************************************/
/*  Problem: a126 "NOI2004 Day1.1.郁闷的出纳员" from NOI2004 Day1 第一题 */
/*  Language: CPP (2780 Bytes)                                                    */
/*  Result: AC(36ms, 5.4MB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2013-01-05 11:07:47                                     */
/**********************************************************************************/


#include <stdio.h>
#include <stdlib.h>
int ST[1048577], M, N = 300005;
char CLR[1048577];
void setST() {
    for(M = 1; M < N+2; M <<= 1);
    int i;
    for(i = 2*M-1; i >= M; i--)
        ST[i] = 0, CLR[i] = 0;
    for(i = M-1; i > 0; i--)
        ST[i] = ST[i<<1]+ST[i<<1|1], CLR[i] = 0;
}
int relax(int k) {
    if(CLR[k]) {
        CLR[k] = 0;
        if(k < M) {
            ST[k<<1] = ST[k<<1|1] = 0;
            CLR[k<<1] = CLR[k<<1|1] = 1;
        }
    }
}
int query(int l, int r, int x, int y, int k) {
    relax(k);
    int m = (l+r)>>1;
    if(l == x && r == y)
        return ST[k];
    if(x > m)
        return query(m+1, r, x, y, k<<1|1);
    else if(y <= m)
        return query(l, m, x, y, k<<1);
    else
        return query(l, m, x, m, k<<1)+
                query(m+1, r, m+1, y, k<<1|1);
} // query(1, M, x, y, 1)
void modifyCLR(int l, int r, int x, int y, int k) {
    relax(k);
    int m = (l+r)>>1;
    if(l == x && r == y) {
        CLR[k] = 1, ST[k] = 0;
        return ;
    }
    if(x > m)
        modifyCLR(m+1, r, x, y, k<<1|1);
    else if(y <= m)
        modifyCLR(l, m, x, y, k<<1);
    else
        modifyCLR(l, m, x, m, k<<1), modifyCLR(m+1, r, m+1, y, k<<1|1);
    ST[k] = ST[k<<1] + ST[k<<1|1];
}
void modify(int s, int val) {
    static int t, l, r, m;
    t = 1;
    l = 0, r = M-1;
    do {
        relax(t);
        ST[t] += val;
        m = (l+r)>>1;
        if(m < s)
            t = t<<1|1, l = m+1;
        else
            t <<= 1, r = m;
    } while(t < 2*M);
}
int main() {
    setST();
    int n, mn, arg;
    int base_line = 100005;
    int tot = 0, leave = 0, tmp;
    char cmd[20];
    scanf("%d %d", &n, &mn);
    while(n--) {
        scanf("%s %d", cmd, &arg);
        if(cmd[0] == 'I') {
            if(arg >= mn) {
                modify(arg+base_line, 1), tot++;
            }
        } else if(cmd[0] == 'A') {
            base_line -= arg; // 基線下降
        } else if(cmd[0] == 'S') {
            if(arg == 0)    continue;
            tmp = query(0, M-1, base_line, base_line+arg+mn-1, 1);
            tot -= tmp, leave += tmp;
            modifyCLR(0, M-1, base_line, base_line+arg+mn-1, 1);
            base_line += arg; // 基線上升
        } else {
            if(tot < arg) {
                puts("-1");
                continue;
            }
            int s;
            arg = tot-arg+1;
            for(s = 1; s < M;) {
                relax(s);
                if(ST[s<<1] < arg)
                    arg -= ST[s<<1], s = s<<1|1;
                else
                    s = s<<1;
            }
            printf("%d\n", s-M-base_line);
        }
    }
    printf("%d\n", leave);
    return 0;
}