|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
30.03.2023, 11:37 | #1 |
Пользователь
Регистрация: 21.11.2022
Сообщений: 84
|
Множество с запросами
Помогите с решение ошибки Failed test #69 of 83. Time limit exceeded
Реализуйте структуру данных для хранения множества целых чисел, поддерживающую запросы добавления, удаления, поиска, а также суммы на отрезке. На вход в данной задаче будет дана последовательность таких запросов. Чтобы гарантировать, что ваша программа обрабатывает каждый запрос по мере поступления (то есть онлайн), каждый запрос будет зависеть от результата выполнения одного из предыдущих запросов. Если бы такой зависимости не было, задачу можно было бы решить оффлайн: сначала прочитать весь вход и сохранить все запросы в каком-нибудь виде, а потом прочитать вход ещё раз, параллельно отвечая на запросы. Формат входа. Изначально множество пусто. Первая строка содержит число запросов n. Каждая из n следующих строк содержит запрос в одном из следующих четырёх форматов: • + i: добавить число f(i) в множество (если оно уже есть, проигнорировать запрос); • - i: удалить число f(i) из множества (если его нет, проигнорировать запрос); • ? i: проверить принадлежность числа f(i) множеству; • s l r: посчитать сумму всех элементов множества, попадающих в отрезок [f(l), f(r)]. Функция f определяется следующим образом. Пусть s — результат последнего запроса суммы на отрезке (если таких запросов ещё не было, то s = 0). Тогда f(x) = (x + s) mod 1 000 000 001 . Формат выхода. Для каждого запроса типа ? i выведите «Found» или «Not found». Для каждого запроса суммы выведите сумму всех элементов множества, попадающих в отрезок [f(l), f(r)]. Гарантируется, что во всех тестах f(l) ≤ f(r). Ограничения. 1 ≤ n ≤ 105 ; 0 ≤ i ≤ 109 Код:
|
01.04.2023, 19:53 | #2 |
Пользователь
Регистрация: 21.11.2022
Сообщений: 84
|
с запросами суммы на отрезке
6.4 Множество с запросами суммы на отрезке
Реализуйте структуру данных для хранения множества целых чисел, поддерживающую запросы добавления, удаления, поиска, а также суммы на отрезке. На вход в данной задаче будет дана последова- тельность таких запросов. Чтобы гарантировать, что ваша программа обрабатывает каждый запрос по мере поступления (то есть онлайн), каждый запрос будет зависеть от результата выполнения одного из предыдущих запросов. Если бы такой зависимости не было, задачу можно было бы решить оффлайн: сначала прочитать весь вход и со- хранить все запросы в каком-нибудь виде, а потом прочитать вход ещё раз, параллельно отвечая на запросы. Формат входа. Изначально множество пусто. Первая строка содер- жит число запросов n. Каждая из n следующих строк содержит запрос в одном из следующих четырёх форматов: • + i: добавить число f (i) в множество (если оно уже есть, проигнорировать запрос); • - i: удалить число f (i) из множества (если его нет, про- игнорировать запрос); • ? i: проверить принадлежность числа f (i) множеству; • s l r: посчитать сумму всех элементов множества, попа- дающих в отрезок [f (l), f (r)]. Функция f определяется следующим образом. Пусть s — резуль- тат последнего запроса суммы на отрезке (если таких запросов ещё не было, то s = 0). Тогда f (x) = (x + s) mod 1 000 000 001 . Формат выхода. Для каждого запроса типа ? i выведите «Found» или «Not found». Для каждого запроса суммы выведите сумму всех элементов множества, попадающих в отрезок [f (l), f (r)]. Га- рантируется, что во всех тестах f (l) ≤ f (r). Ограничения. 1 ≤ n ≤ 105; 0 ≤ i ≤ 109. тесты : Пример. Вход: 15 ? 1 + 1 ? 1 + 2 s 1 2 + 1000000000 ? 1000000000 - 1000000000 ? 1000000000 s 999999999 1000000000 - 2 ? 2 - 0 + 9 s 0 9 Выход: Not found Found 3 Found Not found 1 Not found 10 Для первых пяти запросов s = 0, для следующих пяти — s = 3, для следующих пяти — s = 1. Заданные запросы разворачива- ются в следующие: find(1), add(1), find(1), add(2), sum(1, 2) → 3, add(2), find(2) → Found, del(2), find(2) → Not found, sum(1, 2) → 1, del(3), find(3) → Not found, del(1), add(10), sum(1, 10) → 10. Добав- ление элемента дважды не изменяет множество, как и попытки удалить элемент, которого в множестве нет Пример. Вход: 5 ? 0 + 0 ? 0 - 0 ? 0 Выход: Not found Found Not found Пример. Вход: 5 + 491572259 ? 491572259 ? 899375874 s 310971296 877523306 + 352411209 Выход: Found Not found 491572259 Помогите с решение вот мой код: Код:
|
02.04.2023, 04:30 | #3 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,341
|
Вот так вроде работает:
Код:
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
02.04.2023, 13:18 | #4 |
Пользователь
Регистрация: 21.11.2022
Сообщений: 84
|
падает на 20 тесте а мне он не дан только вот как пример который я скинул
Failed test #20 of 83. Wrong answer |
02.04.2023, 13:28 | #5 |
Пользователь
Регистрация: 21.11.2022
Сообщений: 84
|
почитав пару комментариев задачи ребята говорят проще через AVL дерево вот попробовал реализовать но там 3 ошибки помогите исправить -
Код:
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Программа в Паскале: Даны три множества : Х1, Х2, Х3. Сформировать множество Y=(X1UX2) ⋂(X1UX3)\(X2UX3) и множество Y1 | Агнесска | Помощь студентам | 0 | 06.05.2016 13:50 |
Помощь с запросами | CuMnCoH | SQL, базы данных | 8 | 29.01.2016 23:09 |
Множество, содержащее натуральные числа из первой сотни. Сформировать новое множество из простых чисел первого множества | Aimet | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 16.06.2011 20:50 |
Дано множество А, напечатать четные элементы, входящие в другое множество (Паскаль) | Марийка92 | Помощь студентам | 4 | 03.04.2011 17:38 |
Задано некоторое множество М и множество Т того же типа | dark999 | Помощь студентам | 5 | 01.04.2011 14:17 |