1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#include <iostream>
#include <bitset>
#include <vector>

using odp_t = std::vector< bool >;

template< int N >
struct Zadanie {
	int n;
	int l_op;
	int l_pyt;
	std::vector< std::bitset< N > > zbiory;

	Zadanie(int n, int l_op, int l_pyt): n(n), l_op(l_op), l_pyt(l_pyt) {
		zbiory.resize(n + l_op);
	};

	odp_t zrob();
	void wczytaj();
	odp_t rozwiaz();
};

int main() {
	int n; int l_op; int l_pyt;

	// n          50'000
	// l_op      400'000
	// l_pyt   1'000'000 
	std::cin >> n >> l_op >> l_pyt;

	odp_t odp;

	     if (n <     10) odp = Zadanie<     10 > {n, l_op, l_pyt}.zrob();
	else if (n <    100) odp = Zadanie<    100 > {n, l_op, l_pyt}.zrob();
	else if (n <    200) odp = Zadanie<    200 > {n, l_op, l_pyt}.zrob();
	else if (n <    500) odp = Zadanie<    500 > {n, l_op, l_pyt}.zrob();
	else if (n <  5'000) odp = Zadanie<  5'000 > {n, l_op, l_pyt}.zrob();
	else if (n < 10'000) odp = Zadanie< 10'000 > {n, l_op, l_pyt}.zrob();
	else if (n < 20'000) odp = Zadanie< 20'000 > {n, l_op, l_pyt}.zrob();
	else                 odp = Zadanie< 50'000 > {n, l_op, l_pyt}.zrob();

	for (int i = 0; i < l_pyt; ++i) {
		std::cout << (odp[i] ? "TAK\n" : "NIE\n");	
	}
}

template< int N >
odp_t Zadanie< N >::zrob() {
	wczytaj();
	return rozwiaz();
}

template< int N >
void Zadanie< N >::wczytaj() {
	// poczatkowe
	for (int i = 0; i < n; ++i) {
		auto& zb = this->zbiory[i];

		int start = i + 1;
		int element = start;
		while (element <= n) {
			zb.set(element - 1);
			element += start;
		}

	}

	// operacje
	for (int op = 0; op < l_op; ++op) {
		int opcode; std::cin >> opcode;

		auto& nowy = this->zbiory[n + op];

		if ((opcode == 1) || (opcode == 2)) {
			int zbior_a; std::cin >> zbior_a; zbior_a -= 1;
			int zbior_b; std::cin >> zbior_b; zbior_b -= 1;

			auto const& a = this->zbiory[zbior_a];
			auto const& b = this->zbiory[zbior_b];

			nowy = (opcode == 1) ? (a | b) : (a & b);
		}
		else if(opcode == 3) {
			int zbior_a; std::cin >> zbior_a; zbior_a -= 1;
			auto const& a = this->zbiory[zbior_a];

			nowy = ~a;
		}
	}
}

template< int N >
odp_t Zadanie< N >::rozwiaz() {
	odp_t odp;
	odp.resize(l_pyt);

	for (int i = 0; i < l_pyt; ++i) {
		int zbior; std::cin >> zbior; zbior -= 1;
		int liczba; std::cin >> liczba;
		auto const& z = this->zbiory[zbior];
		odp[i] = z.test(liczba - 1);
	}

	return odp;
}