@Proshka17

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

У меня есть задача:
#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;
}

Как можно решить эту задачу быстрее?
  • Вопрос задан
  • 206 просмотров
Решения вопроса 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-ки не выкинет за пределы, правильно?).
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы