SPOJ: 26914 Sammeln Mango TLE

Question

Problemstellung ist hier verfügbar: http://www.spoj.com/problems/CMG/

Meine Lösung ist dauert nicht mehr als 0,2 Sekunden, auch wenn ich 100.000 Operationen durchführen, aber SPOJ gibt TLE.

SPOJ verwendet g ++ 5.1. Ich führe Code in SunOS - g ++ (GCC) 3.4.3.

Unten ist mein 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; 
} 

Zeitverbrauch für verschiedene Operationen gezeigt, wie in meinem PC folgt.

$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 

Jede der Eingabedateien enthält 100.000 Operationen.

Alle Eingaben sind willkommen, da ich bei der weiteren Optimierung etwas verwirrt bin.

Answer 1

Meine Lösung benötigt konstante Zeit für den Einsatz & Operation entfernen - O (1) und O (log n) Zeit zum Konstruieren sortierten Container (um max zu bestimmen).

Während SPOJ fordert alle drei Operationen in der Größenordnung von 1 (konstante Zeit).