SPOJ - Imiona, przekroczony limit czasowy

Nie mieszczę się w limicie czasowym kiedy wykonuję następujące zadanie: http://pl.spoj.com/problems/NAMES/ Nie mam pomysłów co jeszcze zmienić żeby przyspieszyć działanie programu. W zmiennej "t" przechowuję liczbę testów, chyba tak to się robi ? Macie jakieś wskazówki ?

 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class rekord
{
public:
	string name;
	int counter;
	rekord(string cName, int cCounter)
	{
	     name = cName;
	     counter = cCounter;
  	}
};

bool mySort(rekord p1, rekord p2)
{
     if(p1.counter > p2.counter)
    {
         return true;
    }
    else
    {
         return false;
    }
}

int main() 
{
     int t = 100000;
     vector<string> names;
     vector<rekord> records;
     string input;
     string name;
     int counter = 1;
	

    for(int i = 0; i < t; ++i)
    {
         getline(cin, input);
	 name = input.substr(input.rfind(" ") + 1);
	 transform(name.begin(), name.end(), name.begin(), ::toupper);
	 names.push_back(name);
     }

     sort(names.begin(), names.end());

     for(int i = 0; i < names.size(); ++i)
     {
          counter = 1;
	  name = names[i];
		
	  if(i == (names.size() - 1))
	  {
	       records.push_back(rekord(name, counter));
	  }

	  for(int j = i + 1; j < names.size(); ++j)
	  {
		if(name == names[j])
		{
		     ++counter;
				
		     if(j == (names.size() - 1))
		     {
		          i += (counter - 1);
			  records.push_back(rekord(name, counter));
		     }
				
		}
		else
		{
	              if(counter > 1)
		      {
		           i += (counter - 1);
		      }
				
		      records.push_back(rekord(name, counter));
		      break;
		}
	   }
    }
	
    sort(records.begin(), records.end(), mySort);

    for(int i = 0; i < records.size(); ++i)
    {
         cout<<records[i].name<<" "<<records[i].counter<<endl;
    }
	
    return 0;
}

przeanalizuj soboie mój kod:

#include <algorithm>
#include <string>
#include <map>
#include <vector>
#include <iostream>

using namespace std;

typedef map<string,int> Map;

bool sort_fn(const pair<string,int>& a, const pair<string,int>& b)
{
  return a.second>b.second || (a.second==b.second && lexicographical_compare(a.first.begin(),a.first.end(),b.first.begin(),b.first.end()));
}

int main()
{
  ios_base::sync_with_stdio(0);
  string a,b,imie;
  Map m;
  while (cin >> a >> b >> imie)
    {
      transform(imie.begin(), imie.end(),imie.begin(), ::toupper);
      m[imie]++;
    }
  vector< pair<string,int> > v;
  v.reserve(m.size());
  for (Map::iterator it = m.begin(); it!=m.end(); ++it)
    v.push_back(*it);
  sort(v.begin(),v.end(),sort_fn);
  for (int i=0; i<v.size(); i++)
    {
      cout << v[i].first << ' ' << v[i].second << '\n';
    }
  return 0;
}

ale te zadnie jest głupie. Po co te te nadmiarowe dane? Może po to by wymusić na ludziach używanie C bo operacje wczytywania danych będą tu wąskim gardłem.
Nie wiem jakim cudem zostało zakwalifikowane jako "średni" poziom trudności.

Mam pytanie odnośnie fragmentu kodu:

 
|| (a.second==b.second && lexicographical_compare(a.first.begin(),a.first.end(),b.first.begin(),b.first.end()));

przy returnie: Zakładam, że dane w mapie są ułożone zgodnie z porządkiem alfabetycznym klucza. Jeśli przekładamy potem je po kolei do wektora to po co to sprawdzenie wyszczególnione powyżej ?

ale wyniki trzeba ułożyć zgodnie z najpierw: liczbą wystąpień, a w przypadku remisu w porządku leksykograficznym

Czyli poniższy przykład ilustruje potrzebę sortowania alfabetycznego pomimo, że dane są ułożone wstępnie alfabetycznie w mapie ? :

W mapie:
AA 1
AB 2
AC 2

Tylko return a.second > b.second:

// możliwa sytuacja:

AC 2
AB 2
AA 1

T napisał(a):

Czyli poniższy przykład ilustruje potrzebę sortowania alfabetycznego pomimo, że dane są ułożone wstępnie alfabetycznie w mapie ? :

W mapie:
AA 1
AB 2
AC 2

Tylko return a.second > b.second:

// możliwa sytuacja:

AC 2
AB 2
AA 1

tak. std::sort dobrze sobie radzi z danymi wstępnie posortowanymi

radzę poczytać dokumentację. Nagle się okaże, że jest coś takiego jak stable_sort.