C/C++

Здравствуйте, подскажите у меня совсем ущербный алгоритм. Мне его как-то оптимизировать или что-то другое писать

Здравствуйте, подскажите у меня совсем ущербный алгоритм. Мне его как-то оптимизировать или что-то другое писать. У меня на 9 тесте TL(time limit), надо в 0,25 уложиться, а у меня 0,296 работает.

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


using namespace std;

int N, a, b;

int f( vector<pair<int, int>> sx, pair<int, int> a) {

int l = 0, r = N;

while (r - l > 0) {

int m = (l + r) / 2;

if (sx[m] < a)
l = m;
else if (sx[m] > a)
r = m;
else
return m;
}
return l;
}


int main()
{
int a;

cin >> N;

vector<pair<int, int>> sy(N, make_pair(-1, -1));
vector<pair<int, int>> sx(N, make_pair(-1, -1));

vector<int> g(N, 0);

for(int i = 0; i < N; i++){
cin >> a;
cin >> b;
sx[i].first = a;
sx[i].second = b;
sy[i].first = a;
sy[i].second = b;
}



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

for(int i = 0; i < N; i++){
a = 0;

int h = f(sx, sy[i]);

for(int j = 0; j < h; j++){
if(sx[h].second > sx[j].second || (sx[h].second == sx[j].second && sx[h].first > sx[j].first))
a++;

}

g[a] += 1;

}

for(auto i : g){
cout << i << endl;
}
}


УСЛОВИЕ

Астрономы часто изучают звездные карты, на которых звезды представлены точками на плоскости, и каждая звезда имеет декартовы координаты. Назовем уровнем звезды количество звезд, расположенных не выше и не справа от данной звезды. Астрономы хотят узнать распределение уровней звезд.
Problem illustration

Например, посмотрите на карту, показанную на рисунке выше. Уровень звезды 5 равен 3 (он образуется тремя звездами с номерами 1, 2 и 4). А уровни звезд с номерами 2 и 4 равны 1. На этой карте есть только одна звезда уровня 0, две звезды уровня 1, одна звезда уровня 2 и одна звезда уровня 3.
Вы должны написать программу, которая будет подсчитывать количество звезд каждого уровня на данной карте.

Исходные данные

В первой строке дано целое число N – количество звезд (1 ≤ N ≤ 15000). Следующие N строк содержат целые числа Xi и Yi – координаты звезд (). В одной точке плоскости может быть только одна звезда. Звезды перечислены в порядке возрастания координаты Y. Звезды с одинаковыми координатами Y перечислены в порядке возрастания координаты X.
0 ≤ Xi, Yi ≤ 32000

Результат

Выведите N целых чисел, по одному числу в строке. В первой строке выведите количество звезд уровня 0, во второй – количество звезд уровня 1 и так далее, в последней строке выведите количество звезд уровня N − 1.
Загоняешь все пары в массив, сортируешь по наименьшей (от левого нижнего угла) координате из пары:
pair l < pair r если min(l.x,l.y-max_y) < min(r.x, r.y-max_y) где max_y максимальная y координата из всех точек.
принимаешь начальный level = 0;
После этого бежишь от начала массива и сравниваешь координаты на перегруженное равенство
pair l == pair r если min(l.x,l.y-max_y) == min(r.x, r.y-max_y)
Пока сравнение истино - плюсуешь звезды count_star++.
Как только ложь - значит переход на новый уровень. Сохраняешь пару (level, count_star);
принимаешь новый level = count star, и продолжаешь цикл.

Ну и по мелочи - передавать vector следует по ссылке. Иначе при каждом вызове функции будет создаваться новый вектор, в него все копироваться, отрабатывать и потом удаляться. Так что если сделаете vector <pair<int int>>& sx - будет быстрее.
Али ***
Али ***
51 416
Лучший ответ
Али *** К сожалению методы сортировки указаны не верно. Если одна из координат совпадает - значит равны. Соответственно и < не правильно. Если не совпадают обе координаты то l.x-l.y < r.x-r.y;
32к штук двойным перебором - это 1024М сравнений. Что овердохрена.
Если они уже отсортированы по у, тебе надо просто посмотреть, которые из находящихся в массиве ниже имеют координату, меньше чем х. Это должно быть в 2 раза быстрее. И сортировка твоя тоже лишняя, я не знаток С, но сдаеццо мне, что эти пары могут быть запросто отсортированы по адресу.
BA
Bakyt Asanov
94 397
Ты написал алгоритм за O(n^2), вряд ли такое в 0.25 на таких ограничениях уложится.
Здесь, скорее всего, ожидается алгоритм за O(n log n), нужна структура данных, умеющая за логарифм добавлять единицу в ячейку и считать сумму на префиксе.
В мои годы на такое писали дерево отрезков или фенвика, сейчас мб другая мета, смотри по своему учебному плану.

Плюс ещё замечание, хотя фундаментально это с ускорением вряд ли поможет:
int f( vector<pair<int, int>> sx, pair<int, int> a)
Здесь происходит копирование всего вектора при передаче в аргументв
Используй константную ссылку, хотя бы для sx

А ещё в стандартной библиотеке есть lower_bound и binary_search. Лучше используй их, а то я что-то твоему бинпоиску не сильно доверяю (хотя опять же, скорее всего, бинпоиск как таковой тебе здесь не понадобится).
&#13; Halak
&#13; Halak
36 952
Виктор Василенко Спасибо большое, сейчас буду что ни будь думать.