Как ускорить решение на c++?

Question

[Proshka17]

Добрый день!
Есть задача:

Я написал решение, но получаю TL(Time Limit). Подскажите пожалуйста, как можно ускорить программу?

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

Comments

[Тимур Покровский]

ну во первых не надо везде где только можно использовать векторы

[Proshka17]

Тимур Покровский,
Ну мне показалось такой алгоритм эффективен, у вас есть идея как можно это ускорить?

[Cheburshish]

Не пробовал написать вместо просто названия файла input.txt, написать путь, где лежит файл + input.txt.

[Proshka17]

Зачем?

[Cheburshish]

Затем, что я создал файл input.txt написал в нём
4
1 4
3 2
5 5
2 6
Заменил ifstream f("input.txt"); на ifstream f("C:\\files\\input.txt"); всё нормально заработало .

[Тимур Покровский]

Cheburshish, а ты вопрос читал?

Answer 1

[Mercury13]

Вы тут что-то ухитрились написать, но всё равно n². Потому и TL.

Пусть для каждого поддона длина — большее из измерений, ширина — меньшее. Теперь условие «поддон А можно поставить на поддон Б» упрощается.

Очевидно, что поддоны, которые нельзя поставить друг на друга, будут возрастать по одному измерению и убывать по другому. (Иначе мы сортанём по длине, по ширине тоже обнаруживаем неубывание — и, сюрприз, эти поддоны становятся!)

Получаем список поддонов, которые не становятся ни на кого. Проще всего хранить его в виде set с сортировкой по длине, при этом ширина убывает.

Нам приходит новый поддон. Упорядочиваем координаты, затем ищем в списке equal_range по длине.

Для «БОЛЬШЕЙ» части списка [LOWER_bound, end): наш поддон можно поставить на все эти поддоны по длине, и только на первые из них — по ширине. Если l_b=end, или наш поддон не встаёт на *l_b — добавляем поддон в список. Но не сразу, а после проверки меньшей части.

Для «МЕНЬШЕЙ» части списка [begin, UPPER_bound): все эти поддоны можно поставить на наш поддон по ДЛИНЕ, и только некоторый хвост [some_pallet, upper_bound) — по ширине. Находим этот кусок и исключаем из дерева.

А теперь вопрос: как хакнуть наш set, чтобы можно было проводить поиск за log n и по длине, и по ширине?
А для этого пишем свой объект-сравниватель, который можно переключать между двумя вариантами: length1<length2, либо width1>width2;

P.S. Не очень понятно условие «один поддон становится на другой» — ни из описания, ни из примера. Мой алгоритм — length1 <= length2, width1 <= width2. Если, например, оба строго меньше (length1 < length2, width1 < width2) — то большая часть будет [u_b, end), меньшая — [begin, l_b), и из-за непересечения этих частей не обязательно добавлять в список отложенно.

Comments

[Proshka17]

Добрый день!
Спасибо за ответ!
Идею кажется понял, но не могу сообразить с итераторами.

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

using namespace std;

int type = 0;

struct comparator {

  int operator() (const pair<double, double>& l, const pair<double, double>& r) const {
    if (type == 0) {
      return l.first < r.first;
    }
    else {
      return l.second > r.second;
    }
  }
};

class Solnew {
public:

  set<pair<double, double>, comparator> st;



  void proccess(pair<double, double>& p) {

    auto it1 = st.upper_bound(p);
    int flag = 0;
    if (it1 == st.end() || it1->second <= p.second) {
      st.insert(p);
      flag = 1;
      it1--;
    }

    if (flag && it1 != st.begin()) {
      type = 1;
      auto it2 = st.lower_bound(p);
      type = 0;
      if (it2 == st.end()) {
        it2 = st.begin();
      }
      else {
        it2++;
      }
      st.erase(it2, it1);
    }

  }

};


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;
    pair<double, double> p = { left,right };
    double l = max(p.first, p.second);
    double r = min(p.first, p.second);
    p.first = l;
    p.second = r;
    s.proccess(p);
  }

  cout << s.st.size();



  return 0;
}

При входных данных:
2
52 1
81 20

И при обработке второй пары, it2 почему-то указывает на 52,1, хотя вроде как должен указывать в end.
Не знаете в чем проблема?

[Mercury13]

Proshka17,
Именование — страх и ужос.

if (it2 == st.end()) {
        it2 = st.begin();
      }

Что это за «перенос по кругу»?
С функцией equal_range знаком?

[Proshka17]

Mercury13, Да, знаком вроде.
Я это написал, чтобы если lower_bound не нашел пару, где second не меньше p.second, то это значит, что надо удалять все с начала до it1. Разве нет?

[Mercury13]

Proshka17, Я думал, это какая-то разглючка, связанная с изменением дерева.
Ничего удалять на надо! Это значит у всех, у кого first < p.first, будет second > p.second.
И второе я нашёл — с таким lower_bound надо сверить на всякий случай first. Ведь не исключено, что it2 > it1, но сравнивать такие итераторы невозможно. В таком случае тоже ничего не делаем.

[Proshka17]

Тогда не понял этот кусок:

Для «МЕНЬШЕЙ» части списка [begin, UPPER_bound): все эти поддоны можно поставить на наш поддон по ДЛИНЕ, и только некоторый хвост [some_pallet, upper_bound) — по ширине. Находим этот кусок и исключаем из дерева.

Я понял так:
1)Для каждого поддона, ищем upper_bound. Если он end || upper_bound->second<=p.second, значит, этот поддон, пока нельзя засунуть не в один из рассмотренных и мы вставляем его в set.
2) Только если мы вставили поддон:
Ищем lower_bound по second`ам. Lower_bound точно укажет на значение ниже(которое находится ближе к началу) it1, иначе, мы бы не вставили текущий поддон в set.
Теперь удаляем все, что между it1 и lower_bound, потому что все эти поддоны входят в только что добавленный поддон.
Поправьте пожалуйста, если я не правильно понял.

[Mercury13]

Proshka17,
Как я уже написал, надо чётко понимать, какое условие «один поддон встанет на другой». Если меньше по обоим измерениям — то [begin, LOWER_bound). Мы ищем поддоны, которые встанут на наш.
Выяснил, что можно обойтись без трюкачества с условием сравнения — просто…
1. Если it1 = begin, BREAK
2. --it1
3. Если этот поддон НЕ встанет на наш, BREAK
4. it1 := erase(it1).
5. Повторить.
Каждая итерация цикла — log n, при этом итераций НА ВСЮ ПРОГРАММУ не больше n.
Цикл на условие «меньше по обоим измерениям», если условие другое — то и цикл другой.

[Proshka17]

Я доделал, все получилось!
Большое спасибо за помошь.
Есть еще одна задачка, там WA, по асимптотике там вроде все хорошо. Буду очень благодарен, если посмотрите, я вас пригласил как эксперта.