SPOJ：26914收集芒果TLE

Question

这里有问题说明：http://www.spoj.com/problems/CMG/

即使我执行了100000次操作，但SPOJ赋予TLE的时间，我的解决方案也不会超过0.2秒。

SPOJ使用g ++ 5.1。我正在SunOS中运行代码-g ++（GCC）3.4.3。

下面是我的代码：

    //Collecting Mango Problem
#include <cstring>
#include <stdlib.h>
#include <sstream>
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;
int *max_mango,*IDX;
vector <int> mango_basket;
void Throw();
void Add(int mango);
int Max();
char operation[9],buf[5];
ostringstream buffer1;
multiset<int> mymultiset;
multiset<int>::iterator it;
string s="";
vector <char> buffer2;

void Add(int x){
        mango_basket.push_back(x);
        mymultiset.insert(x);
}

void Throw(){
        it = mymultiset.find(mango_basket.back());
        mango_basket.pop_back();
        mymultiset.erase(it);
}

int Max(){
    it = mymultiset.end();
    --it;
    return *it;
}

int main ()
{
        int T,N,x;
        scanf("%d",&T);
        if (( 1 <= T ) == (T <= 25)){
                for (int i=0;i<T;i++){
                if(i != 0) {buffer1 << "\nCase " << i + 1 << ":";}
                else {buffer1 << "Case " << i + 1 << ":";}
                scanf("%d",&N);
                scanf("%c",operation);
                mango_basket.clear();
                mymultiset.clear();
                if ((1 <= N) == (N <= 100000)){
                for (int j=0;j<N;j++){
                fgets (operation, 9, stdin);
                switch (operation[0])
                {
                        case 'A':
                        {
                                x=atoi(operation + 2);
                                if ((1 <= x) == (x <= 100000)){
                                Add(x);
                                }
                        }
                        break;
                        case 'R':
                        {
                                if (!mango_basket.empty()){
                                Throw();
                        }
                        }
                        break;
                        case 'Q':
                        {
                                if(!mymultiset.empty()){
                                buffer1 << '\n' << Max();
                                }
                                else{
                                buffer1 << "\nEmpty";
                                }
                        }
                        break;
                }
                }}

        fputs(buffer1.str().c_str(), stdout);
        buffer1.str("");
        buffer1.clear();
        }
        }
        return 0;
}

在我的电脑上显示如下所示的不同操作的时间消耗。

$time ./a.out < ADD_MAX

real    0m0.15s
user    0m0.09s
sys     0m0.00s

$time ./a.out < ADD_REMOVE
Case 1:
1
real    0m0.16s
user    0m0.10s
sys     0m0.00s

$time ./a.out < ADD
Case 1:
99999
real    0m0.19s
user    0m0.14s
sys     0m0.00s

$time ./a.out < ADD_MAX_REMOVE

real    0m0.16s
user    0m0.10s
sys     0m0.00s

每个输入文件包含100,000个操作。

欢迎输入任何内容，因为我对进一步优化有些困惑。

Answer 1

[我的解决方案需要固定的时间进行插入和删除操作-O（1）和O（log n）的时间来构造排序后的容器（以确定最大值）。

然而，SPOJ要求这三个操作全部为1（恒定时间）。

Answer 2

我已经使用细分树实现了。解决方案：Collecting Mango 注： 使用FAST输入/输出方法 s。