SPOJ: 26914 Collecting Mango TLE

Question

Problem statement is available here: http://www.spoj.com/problems/CMG/

My solution doesn't takes more than 0.2 seconds even when I perform 100000 operations but SPOJ gives TLE.

SPOJ uses g++ 5.1. I am running code in SunOS - g++ (GCC) 3.4.3.

Below is my code:

    //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 consumption for different operations shown as follows in my PC.

$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

Each of the input file contains 100,000 operations.

Any inputs are welcome as I am bit confused on optimizing further.

Answer 1

My Solution takes constant time for insert & remove operation - O(1) and O(log n) time for constructing sorted container (to determine max).

Whereas, SPOJ demands all the three operations to be of the order of 1(constant time).