|
|
|
|
|
|
|
Вернуться
| 1 Меньшиков Фёдор Владимирович, 22 июня 2018 г. 23:07:41 | |
|
Можно sqrt-декомпозицию применить. Для каждой группы хранить количество ещё живых элементов в этой группе.
|
|
|
| 2 Неизвестный, 21 июня 2018 г. 20:56:25 | |
В этой задаче нужно получать элемент по номеру. Этого set не умеет. Да я так же думал, но я нашёл фунцию доступа до елемента по индексу k ,называется next(a.begin(),k) но она работает в O(n) что очень плохо.
|
|
|
| 3 Неизвестный, 21 июня 2018 г. 20:34:51 | |
|
Понятно,ну буду дальше развиватся,просто както не верится что 62 человека реализовали декартовое дерево для етой задачи.
|
|
|
| 4 Меньшиков Фёдор Владимирович, 21 июня 2018 г. 17:32:12 | |
|
Да, несколько элементов подряд из set можно удалить довольно эффективно - за O(logn + k), где n - размер дерева, а k - число удаляемых элементов. Но! В этой задаче нужно получать элемент по номеру. Этого set не умеет. Умеет или декартово дерево, или https ://codeforces.com/blog/entry/11080
|
|
|
| 5 Неизвестный, 18 июня 2018 г. 17:03:43 | |
|
И еще мне говорили что если удалять из контейнера set в С++, то оно идёт в log(n) час, распространяется ето на диапазон который нужно удалить или нет?
|
|
|
| 6 Неизвестный, 18 июня 2018 г. 16:58:27 | |
|
Большое спасибо!!!
|
|
|
| 7 Меньшиков Фёдор Владимирович, 18 июня 2018 г. 15:51:10 | |
|
Почитайте на e-maxx про декартово дерево. Это самая стандартная структура данных для решения этой задачи.
|
|
|
| 8 Неизвестный, 17 июня 2018 г. 19:43:51 | |
Вот моя реализация. Идёт на лимит на 5 тесте.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int i,n,k,l,r,j;
cin >> n >> k;
vector<int> a(n+1);
for (i = 1; i < a.size(); i++) {
a[i] = i;
}
for (i = 0; i < k; i++) {
cin >> l >> r;
a.erase(a.begin()+l,a.begin()+r+1);
}
cout << a.size()-1 <<endl;
for (i = 1; i < a.size(); i++) {
cout << a[i] << ' ';
}
return 0;
}
|
|
|
| 9 Неизвестный, 17 июня 2018 г. 19:33:56 | |
Я очень извиняюсь там длина мисава 3*10^5
|
|
|
| 10 Неизвестный, 17 июня 2018 г. 19:26:28 | |
Извините. Начну с начала: дано два числа n, k <=10^15, тогда в k радках по два числа l , r - номера елементов масива чисел от 1 до n от которых нужно удалять елементы. Наведу наглядный пример:
Пусть n=10, а k=3
Тогда у k строках по два числа, l та r (l <= r). Гарантируется что на каждом етапе есть елементы которые можна удалить.
1 2 - удалили елементы от 1 до 2,остались 3 4 5 6 7 8 9 10.
4 5 - удалили в етом же масиве елементы от 4 до 5,остались 3 4 5 8 9 10.
3 5 - и еще раз удалили елементы с индексами от 3 до 5, и остались 3 4 10!Ето и есть же конечный масив.
После етих запросов надо вивести длину конечного масива,и елеметы которые останутся после удаления.
Вывод:
3
3 4 10
Думаю будёт понятно,и да нам не надо вводить масив, как вы говорили ранее, просто у меня первое такое решение пришло в голову, ну а как иначе?Может вы подскажите буду очень и очень благодарен,у вас очень хороший сайт на котором можно только прогресировать)))
|
|
|
| 11 Меньшиков Фёдор Владимирович, 16 июня 2018 г. 22:56:16 | |
|
Если Вас просят ввести 10^15 чисел - то задача заведомо не имеет решения. Иначе нужно точное условие задачи для её решения, а не туманное описание.
|
|
|
| 12 Неизвестный, 16 июня 2018 г. 15:02:27 | |
|
А и еще там даны числа от 1 до k <=10^15, ну и как говорилось ранее n запросов на удаления. У меня стаж 1,5 года но с такими задачами я еще не сталкивался.
|
|
|
| 13 Меньшиков Фёдор Владимирович, 16 июня 2018 г. 8:02:09 | |
|
Учитывая, что за секунду можно выполнить порядка 10^8 операций, 10^15 случайных запросов за 2 секунды выполнить нельзя никак. И ввести тоже столько нельзя. Значит запросы удаления не случайны. Значит нужно использовать эту неслучайность.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
