Как решить задачу c++?

Question

[Proshka17]

У меня есть задача:

#include <iostream>
#include <fstream>
using namespace std;

class Sol {
public:



	void doit(long from, long to, long left, long right, long* vec) {
		int check = 1;
		for (long i = left - 1; i <= right - 1; ++i) {
        if (vec[i] != from) {
        cout << "0\n";
        return;
        }
		}
		for (long i = left - 1; i <= right - 1; ++i) {
			vec[i] = to;
		}
		cout << "1\n";

	}
};


int main() {
	ifstream f("input.txt");
	Sol s;
	long chunc;
	long serv;
	long count;
	f >> chunc;
	f >> serv;
	f >> count;
	long* vec = new long[chunc];
	for (long i = 0; i < chunc; ++i) {
		long c;
		f >> c;
		vec[i] = c;
	}
	for (long i = 0; i < count; ++i) {
		long from;
		long to;
		long l;
		long r;
		f >> from;
		f >> to;
		f >> l;
		f >> r;
		s.doit(from, to, l, r, vec);
	}


	return 0;
}

Как можно решить эту задачу быстрее?

Comments

[Adamos]

Например, сделать все аргументы функции членами класса и не создавать их в цикле.
Выше тоже выкинуть создание переменной и считывать значение сразу в элемент массива.
Перенести чтение из файла в конструктор класса, раз уж он все равно используется.
Накапливать в классе вывод вместо того, чтобы каждый символ выводить отдельно.

[Proshka17]

Adamos, добрый день!
Я думаю, что нужно логическое изменение в алгоритме

[Roman]

putc вместо cout
А еще лучше возвращать значение и потом выводить.

[Adamos]

Proshka17, я не думаю, что оно кому-то, кроме вас, нужно настолько, чтобы читать ваши радужные картинки.

[Proshka17]

Roman, Добрый день!
Все так же Time Limit, может я допустил алгоритмическую ошибку?

Answer 1

[Mercury13]

У вас нормальное (хоть и корявое по части кода, я за такой код пинаю!) лобовое решение. Очевидно, придётся наладить какой-нибудь ускоритель, позволяющий выполнить запрос быстрее, чем за O(n).

Моё предложение: map (ради скорости можно прикрутить собственный аллокатор типа «объектный пул», благо кол-во блоков данных ограничено сверху 100k), показывающий, например, для третьего примера картинку «1→1, 2→2, 3→3, 4→4, 5→5». После первой транзакции — «1→2, 3→3, 4→4, 5→5». Поиск в этом map’е — upper_bound минус единичка (даже поиск 1-цы укажет или на второй элемент, или за первый). Сможете наладить методику разделения и склеивания диапазонов?

Можно и наоборот: 2→1, 3→3, 4→4, 5→5. Поиск в таком map’е — lower_bound (даже поиск 5-ки не выкинет за пределы, правильно?).

Comments

[Mercury13]

Да, я забыл про номер сервера. Там же, в second, разумеется.
НЕЛЬЗЯ; только set/map — иначе не выдерживается асимптотическая сложность. Тебя же это прижало, правильно — перенос двух, трёх, четырёх блоков должен быть эффективнее, чем одного.

[Mercury13]

Код страшен, как чёрт: я вижу код начинающего, который пробует сделать сложную систему.
Побочные эффекты, возврат значения в консоль, простыня кода без попыток её прокомментировать или структурировать, и многое другое.

[Mercury13]

А с map — там всё просто.

struct ServerInfo {
  int right, server;
}
using MChunks = std::map<int, ServerInfo>;
MChunks chunks;

[Mercury13]

Proshka17,
Повторяю: не выдерживается асимптотическая сложность.
И этот код тоже не выдерживает: map является деревом поиска, а вы по ней делаете линейный поиск.

[Mercury13]

Связные списки, если объект мал и «туп», не оправданы. Vector и тот лучше.
Почему map: у него вставка, поиск и удаление за O(log n).
Элементы в map всегда отсортированы (так действует любое дерево поиска, самобалансирующееся или нет). Функции поиска в map называются так же, как стандартные функции двоичного поиска — lower_bound и upper_bound. Это начало и конец диапазона равных: если в multimap’е будет 1,3,3,3,5,7, то lower_bound 3-ки даст первую 3-ку, upper_bound — элемент за ними (5). Если ищем что-то отсутствующее — например, 6 — оба укажут на 7-ку. Учите, как они работают, эти функции, это важно!

[Mercury13]

Ну а связным спискам есть два применения.
1. Объекты уже созданы, и хотелось бы их группировать то так, то этак. Например, в структуре данных «объектный пул».
2. Объекты плохо выдерживают перенос. Жёсткое реальное время, какие-нибудь системные штучки, или просто много… И то часто лучше deque или vector<unique_ptr<>>.

[Mercury13]

А тут уже ищите, где вы неправильно делаете поиск.
Допустим, у нас 5 блоков на одном сервере — 1→(конец 5, сервер 1), правильно?
Тогда lower_bound блока 3 даёт end(), и мгновенно выдаётся результат «транзакция невозможна».
А я писал, как должен проводиться поиск в этом варианте, разуйте глаза.

[Proshka17]

Mercury13, Этот кейс поправил, теперь ошибка на 43 тесте

[Mercury13]

У вас настолько страшный код, что глаза ломаются разбирать, где тут ошибка.

[Mercury13]

Ты даже содрать тупо не можешь.
1. UPPER_bound.
2. Если begin() — выдать ошибку. Иначе --.

[Mercury13]

Хотя я посмотрел на ваш поиск, наверно, он правильный, но мудрё-ёный…

[Mercury13]

Я пока вижу ошибку в ветке с совпадением left и right в таком случае:
1…1, сервер 1
2…2, сервер 2
3…3 сервер 1
Переносим 2…2 на сервер 1 — всё должно спрессовать в 1…3, сервер 1. Не сделает.

Повторяю, увижу такой код в своём проекте — пинать буду!

[Proshka17]

Mercury13, Да, спасибо.Он добавляет 1-3 промежуток, но не удаляет 2-2 промежуток. Исправил, но ошибка осталась

[Mercury13]

Моя версия. Усложним задачу — аллокатор нормальный и требуется минимально вызывать new/delete.

struct TempRange {
  int left = 0, right = 0, server = 0;
}

struct TempRanges
{
   TempRange data[6];  // с запасом на один, реально нужно пять
   int size = 0;

   void add(int left, int right, int server);
   // напишешь с обработкой пустых диапазонов и правильной склейкой?
   // Обрабатывать будем только слева направо
   void add(iterator) { add(iterator->first, iterator->second.right, iterator->second.server); }
}

// Вот мы получили it
TempRanges tmp;

iterator itLeft = it;
if (itLeft != map.begin()) {
  --itLeft;
  tmp.add(itLeft);
}
tmp.add(it->first, left - 1, from);
tmp.add(left, right, to);
tmp.add(right + 1, it->second.right, from);

iterator itRight = it;
++itRight;
if (itRight != map.end()) {
  tmp.add(itRight);
  ++itRight;
}

// Пошла замена, ломать можно только [itLeft, itRight)
it = itLeft;
for (int i = 0; i < tmp.size(); ++tmp) {
  TempRange& range = tmp.data[i];
  // Удалим лишнее
  while (it != itRight && it->first < range.left) {
    auto it2 = it;
    ++it;
    map.erase(it2);
  }
  // Заменим/добавим
  if (it != itRight && it->first == range.left) {
    it->second.right = range.right;
    it->second.server = range.server;
  } else {
    ++it;
    // Вставка с хинтом, немного выиграет!
    it = map.emplace_hint(it, range.left, ValueType { range.right, range.server } );
    ++it;
  }
}
// Удалим остаток
map.erase(it, itRight);