2. Ranges - Имам time limit единия тест - Софтуерен университет

DimovIvan 16 Точки

2. Ranges - Имам time limit единия тест

Единия тест не ми минава за време. Очевидно не съм написал оптимално кода. Помогнете ми да забързам нещата, моля!

https://pastebin.com/PNetyeq5

A range is a pair of integer numbers – let’s say that from and to form the range [from, to].

If an integer number x is such that from <= x <= to, then we say that x is inside the range [from, to], or that the range [from, to] contains x.

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.

You are also given a sequence of integer numbers – let’s call them check numbers.

For each of the check numbers, print "in" if the number is inside any range, and "out" otherwise (i.e. if no range contains the number).

NOTE: there will be a large number of ranges and an even larger number of integer numbers.

Input

The input will be separated into two parts.

The first part will contain the ranges, each described as two integer numbers on a separate line of the standard input (the from and to of the range), until a line containing only the symbol '.' (dot) is reached.

After that, each line of the standard input will contain exactly one check number, until a line containing only the symbol '.' (dot) is reached.

Output

For each check number in the input, print "in" if that number is contained in any range, or "out" if no range contains that number.

Restrictions

There will be between 1 and 10000 ranges (inclusive).

There will be between 1 and 100000 check numbers (inclusive).

For every range, from <= to.

In 30% of the tests, there will be no more than 10 ranges and 10 numbers.

The total running time of your program should be no more than 0.4s

The total memory allowed for use by your program is 8MB

Тагове:

08/05/2022 23:01:32 C++ Advanced

MartinBG 4803 Точки

Решението е бавно, защото за всяко число се обхождат всички ranges (това е най-лошият сценарий, но точно той ни инересува), а при голям брой ranges (до 10000 по условие) и числа (до 100000), ще направим до 10000 * 100000 проверки. С други думи, сложността на използвания алгоритъм е M * N (ranges * numbers).

За да зaбързаме нещата ни трябва контейнер/структура, която да ни дава бърз отговор дали в нея има елемент, който отговаря на конкретно изискване (в случая да е по-голям или по-малък от някаква стойност). vector не е подходящ контейнер в случая, защото не предлага подобна функционалност наготово. За спорта, ако се сортира и се използва двоично търсене и custom логика би трябвало да стане, но set и map ни дават това наготово с помощтта на lower_bound и upper_bound методите си, а сложността на алгоритъма ще се промени на log(M) * N, което е на порядъци по-бързо.

Няколко подсказки как да се подходи към решението:

- два map-a (напр. starts и ends), като за key се използва съответно началото и края на всеки range, a като value - нещо уникално за всеки range (например id според поредността на въвеждането им: 0, 1, 2, 3 и т.н.)

- с lower_bound и upper_bound търсим числата във всеки от map-овете, а при намиране остава да проверим дали попаденията са от един и същи range (т.е. имат еднo и същo id):

    auto start = starts.upper_bound(value);
    auto end = ends.lower_bound(value);
    bool isInRange = start != starts.begin() && ((--start)->second == end->second);

09/05/2022 01:16:10 09/05/2022 01:19:15

DimovIvan 16 Точки

Много благодаря за насоките!

10/05/2022 06:02:29