How to speed up a solution in c++?

Question

C++ / C#

Good afternoon!
There is a task:

I wrote a solution, but I get TL(Time Limit). Please tell me how can I speed up the program?

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <chrono>
#include <set>
#include <fstream>

using namespace std;


///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



vector<vector<double>> vec1;

static bool func(vector<double>& e1, vector<double>& e2) {
  return (e1[0] == e2[0]) ? e1[1] > e2[1]:e1[0] < e2[0];
}

class Solnew {
public:

  map<double, double> st1;
  vector<long long> more;


  double bad = 0;

  void Doit() {

    sort(vec1.begin(), vec1.end(), func);

    for (long long i = vec1.size() - 1; i >= 0; --i) {
      auto it = st1.upper_bound(vec1[i][1]);
      if (it == st1.end()) more.push_back(i);
      st1.emplace(vec1[i][1], vec1[i][0]);
    }

    
    for (long long k = more.size() - 1; k >= 0; --k) {
      long long i = more[k];

      auto it = st1.upper_bound(vec1[i][0]);
      int flag = 0;
      for (auto iter = it; iter != st1.end() & !flag; ++iter) {
        if (vec1[i][1] < iter->second) flag = 1;
      }

      if (!flag) {
        bad++;
      }

    }

  }

};


int main() {

  ifstream f("input.txt");
  Solnew s;
  double count;
  f >> count;

  for (double i = 0; i < count; ++i) {
    double left;
    double right;
    f >> left;
    f >> right;
    vector<double> tmp = {left,right};
    vec1.push_back(tmp);
  }
  s.Doit();
  cout << s.bad;




  return 0;
}

Answer 1

You managed to write something here, but still n². That's why TL.
For each pallet, let the length be the larger of the dimensions, and the width the smaller. Now the condition "pallet A can be put on pallet B" is simplified.
Obviously, pallets that cannot be stacked on top of each other will increase in one dimension and decrease in another. (Otherwise, we sort by length, we also find non-decreasing by width - and, surprise, these pallets become!)
We get a list of pallets that do not fit on anyone. The easiest way is to store it as a set sorted by length, while the width decreases.
We've got a new pallet. We order the coordinates, then look in the equal_range list by length.
For the “BIGGER” part of the list [LOWER_bound, end): our pallet can be placed on all of these pallets in length, and only on the first of them in width. If l_b=end, or our pallet does not fit *l_b, we add the pallet to the list. But not immediately, but after checking a smaller part.
For the "SMALLER" part of the list [begin, UPPER_bound): all these pallets can be put on our pallet in LENGTH, and only some tail [some_pallet, upper_bound) in width. We find this piece and exclude it from the tree.
And now the question is: how to hack our set so that we can search for log n both in length and in width?
And for this we write our own comparer object, which can be switched between two options: length1<length2, or width1>width2;
PS It is not very clear the condition "one pallet is placed on another" - neither from the description, nor from the example. My algorithm is length1 <= length2, width1 <= width2. If, for example, both are strictly less than (length1 < length2, width1 < width2), then the larger part will be [u_b, end), the smaller one will be [begin, l_b), and because of the non-intersection of these parts, it is not necessary to add to the list deferred.