Removing the largest values encountered so far in a list

The problem is, in summary:


A set of values will be given. Whenever the input is -1, the largest number from the values inputted until then needs to be printed, and is then deleted.

Here is the code that I wrote for it:

#include
#include
#include

using namespace std;
int main()
{
  int val;
  int N, M, x=0, i=0;
  vector visits;
  cin>>N>>M;
  for(x=0; x>val;
    visits.push_back(val);
     if(val==-1)
      {

         cout<<*max_element(visits.begin(), visits.end())<<endl;
         i++;
         visits.erase(max_element(visits.begin(), visits.end()));
      }
  }

    return 0;
}

The program gives correct answers, but it exceeds the time limit for some of the test cases. The test data isn't given, so I don't know for what size of test data it fails. Is there some other way by which I can optimize my code?

You are using a C++ compiler!

So you should also use its features:

• don't declare all variables up front but as late as possible

• don't using namespace std; that only gives you trouble later on

• you don't need to return 0; at the end of main

Formatting

Your formatting can be improved. You should use more spaces especially around (binary) operators, this makes it easier to parse (or rather tokenize) the code with your eye.

Naming

You have nearly only single letter names which is bad. The fact that two of them look like macro names does not make it better. Consider:

• N -> populationHeadCount

• M -> executionCount

• val -> currentVisitorWealth

• visits -> stillLivingWealthiest

Unused variable

The variable i is initialized and incremented but never read.

Inserting "the king"

Your code unconditionally inserts the wealth val even if it is the king (-1), thus introducing even more entries in visits.

Speed up

Reading rules more closely than you have given them here yields:


You may assume that no two citizens have the same wealth.

Which makes this problem a perfect fit for an std::set (as mentioned by Loki):

#include 
#include 
#include 

int main() {
  int populationHeadCount, expectedExecutionCount;
  std::cin >> populationHeadCount >> expectedExecutionCount;
  std::set stillLivingWealthiest;
  int executionNumber = 0;
  while (executionNumber > currentVisitorWealth;
    if (currentVisitorWealth == -1) {
      std::cout << *--stillLivingWealthiest.end() << std::endl;
      stillLivingWealthiest.erase(--stillLivingWealthiest.end());
      ++executionNumber;
    } else {
      stillLivingWealthiest.insert(currentVisitorWealth);
    }
  }
}

Explanation: A std::set stores the elements sorted from minimum to maximum, so we only need to look at the end to get and delete the maximal element.

StackExchange Code Review Q#61772, answer score: 8