@Elnurhan

Как оптимизировать этот код?

Участвовал в олимпиаде, которая уже завершилась, и попалось одно задание(приложил фотку):5e712be95137d867246554.png
С виду задача простая, но код, который я написал в первый раз не прошёл из-за ограничений времени. Как только я не пытался его оптимизировать - ничего не вышло. Остановился на таком варианте:
#include <bits/stdc++.h>
#include <unordered_map> 
 
using namespace std;
 
int main() {
	int q, type, x;
	cin >> q;
 
	unordered_map <int, int> coll;
	for (int i = 0; i < q; ++i) {
		cin >> type >> x;
 
		if (type == 1) coll[x] += 1;
		else if (type == 2) coll[x] -= 1;
		else {
			int count = 0;
			for (const auto& kv : coll) {
				if (kv.second != 0 && kv.first % x == 0) {
					count++;
				}
			}
			cout << count << "\n";
		}
	}
}


Но он тоже не прошёл из-за времени. Как можно решить эту задачу быстрее?
  • Вопрос задан
  • 139 просмотров
Решения вопроса 1
longclaps
@longclaps
В среднем у числа в диапазоне 1..10^6 14 делителей, включая единицу (максимум - 240 делителей у 720720).
Предпосчитать все делители всех чисел диапазона можно очень быстро, даже на питоне.
Заводишь массив длины 10^6+1 и на запросах type 1/2 инкрементируешь/декрементируешь его ячейки, соответствующие делителям x (но только в том случае, если сам x прибывает/исчезает из коллекции, иначе не надо).
На запросах type 3 выясняешь, что в ячейке массива по индексу x.

А этот код оптимизировать не надо.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
30 мар. 2020, в 10:09
500 руб./в час
30 мар. 2020, в 09:48
120000 руб./за проект
30 мар. 2020, в 09:33
10000 руб./за проект