Are you encountering challenges searching for Reliable Case Study Writing Service? Look no further; Legitimate Online Case Study Services has a solution to your Case Study Assignment Writing Services.

Привет!

1. Ако се очаква да четеш или печаташ повече на брой входни/изходни данни, то за да стане по-бързо използвай следното преди четенето:

std::cin.sync_with_stdio(false);
std::cout.sync_with_stdio(false);

или

std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);

https://stackoverflow.com/questions/31162367/significance-of-ios-basesync-with-stdiofalse-cin-tienull

2. Бих те посъветвал да използваш lower_bound на вместо обхождане на ranges чрез Range-based for loop, като за целта колекцията ти трябва да е сортирана:

std::vector<std::pair<int, int>> ranges;

std::sort(ranges.begin(), ranges.end());

auto iterator = lower_bound(ranges.begin(), ranges.end(), std::make_pair(num, num));

http://www.cplusplus.com/reference/algorithm/lower_bound/

(По прицип може да минеш и без pair<> тъй като нямаш пресичане на отделните интервали)

( lower_bound ще ти върне итератор към коткретния pair ако first == num или към следващия pair ако first < num.

Имаш възможност да използаш iterator--;

int id = std::distance(ranges.begin(), iterator); - индекс

if (num >= ranges.at(id).first && num <= ranges.at(id).second){
...
}else{
...
})

3. Може директо да четеш число от конзолата, вместо да го записваш във вектор и след това да го проверяваш дали е в даден интервал.

4. Има ли някаква причина да използаваш пойтър към pair?

std::shared_ptr<std::pair<int, int>>

Поздрави!

Решението е бавно, защото за всяко число се обхождат всички* ranges, т.е. алгоритъмът е със сложност O(N * R), където N - брой числа, R - брой ranges.

По условие в 30% от тестовете N и R са с до 10 елемента, т.е. имаме до 100 проверки (N * R = 10 * 10 = 100).

За останалите тестове, N може да е до 100 000, а R - до 10 000, т.е получаваме 1 000 000 000 проверки за най-лошият сценарий. 

Трябва да потърсиш алтернативно решение, при което няма толкова силна зависимост между N и R.

В условието се казва, че няма застъпване в ranges: 

You are given a set of ranges, in which no two ranges intersect. That means that no range contains the from or to of another range.
 

Това е важно, защото ни позволява да сортираме ranges еднократно, а търсенето в сортирани колекции е с логаритмична сложност (напр. за 10 000 елемента ще имаме ~13.3 проверки).

Оптимален алгоритъм за тази задача ще има сложност O(N * log(R)), което при лимитите дадени в условието, е около 750 пъти по-бързо от O(N * R).

Algorithm library има полезни функции, които може да спестят част от кода, например:

• lower_bound
• upper_bound
• equal_range

[*] Разбира се, ако числото е в първия range, не се обхождат останалите, но правилото е да се гледа най-лошия сценарий, т.е. когато числото не е в никой range, или е в последният такъв. 

Заформи се клуб  "30/100"  в групата явно. И аз имам същите проблеми със скоростта а вече 4 решения написах. В нито едно от тях не се избягва проверката отнемаща R*N операции ( за всяко число да се обходят всички обхвати ) и ми се струва , че основният проблем е там както каза Мартин . Как точно да го заобиколим обаче не се сещам до момента