SPOJ: 26914 Collecte Mango TLE

Question

L'énoncé du problème est disponible ici: http://www.spoj.com/problems/CMG/

Ma solution ne prend plus de 0,2 secondes, même si j'effectue 100000 opérations, mais SPOJ donne TLE.

SPOJ utilise g ++ 5.1. Je cours le code dans SunOS - g ++ (GCC) 3.4.3.

est mon code ci-dessous:

//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; 
} 

consommation de temps pour différentes opérations indiquées comme suit dans mon 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 

Chaque fichier d'entrée contient 100 000 opérations.

Toutes les entrées sont les bienvenus car je suis un peu confus sur l'optimisation plus loin.

Answer 1

Ma solution prend un temps constant pour l'insertion & enlève l'opération - O (1) et O (log n) temps pour la construction du conteneur trié (pour déterminer max).

Considérant que, SPOJ exige que toutes les trois opérations soient de l'ordre de 1 (temps constant).