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

Question

[Elnurhan]

Участвовал в олимпиаде, которая уже завершилась, и попалось одно задание(приложил фотку):
С виду задача простая, но код, который я написал в первый раз не прошёл из-за ограничений времени. Как только я не пытался его оптимизировать - ничего не вышло. Остановился на таком варианте:

#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";
		}
	}
}

Но он тоже не прошёл из-за времени. Как можно решить эту задачу быстрее?

Comments

[Saboteur]

Я бы для такой задачи выбрал case
А можно узнать какие были тайминги и за сколько ваша отработала на олимпиадном железе?

Answer 1

[longclaps]

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

А этот код оптимизировать не надо.