Submission #866701

#	Time	Username	Problem	Language	Result	Execution time	Memory
866701		TAhmed33	Radio (COCI22_radio)	C++98	110 / 110	581 ms	112684 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 25;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
struct SegmentTree {
	int tree[2 * MAXN];
	void build (int l, int r, int node) {
		if (l == r) {
			tree[node] = MAXN;
		} else {
			build(l, mid, tl); build(mid + 1, r, tr);
			tree[node] = min(tree[tl], tree[tr]);
		}
	}
	void update (int l, int r, int a, int b, bool flag, int node) {
		if (l > a || r < a) return;
		if (l == r) {
			if (flag) tree[node] = b;
			else tree[node] = min(tree[node], b);
			return;
		}
		update(l, mid, a, b, flag, tl); update(mid + 1, r, a, b, flag, tr);
		tree[node] = min(tree[tl], tree[tr]);
	}
	int get (int l, int r, int a, int b, int node) {
		if (l > b || r < a) return MAXN;
		if (l >= a && r <= b) return tree[node];
		return min(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
	}
} cur;
int sieve[MAXN];
vector <int> get (int x) {
	vector <int> y;
	while (x > 1) {
		y.push_back(sieve[x]);
		x /= sieve[x];
	}
	y.resize(unique(y.begin(), y.end()) - y.begin());
	return y;
}
int sze[MAXN], lst[MAXN][7];
int n, q;
set <int> active[MAXN];
bitset <MAXN> isactive;
void activate (int x) {
	isactive[x] = 1;
	int mn = MAXN;
	for (int i = 0; i < sze[x]; i++) {
		if (!active[lst[x][i]].empty()) {
			auto g = active[lst[x][i]].lower_bound(x);
			if (g != active[lst[x][i]].end()) mn = min(mn, *g);
			if (g != active[lst[x][i]].begin()) {
				g--;
				cur.update(1, n, *g, x, 0, 1);
			}
		}
		active[lst[x][i]].insert(x);
	}
	cur.update(1, n, x, mn, 1, 1);
} 
void change (int x) {
	int mn = MAXN;
	for (int i = 0; i < sze[x]; i++) {
		if (active[lst[x][i]].empty()) continue;
		auto g = active[lst[x][i]].upper_bound(x); 
		if (g != active[lst[x][i]].end()) mn = min(mn, *g);
	}
	cur.update(1, n, x, mn, 1, 1);
}
void deactivate (int x) {
	isactive[x] = 0;
	cur.update(1, n, x, MAXN, 1, 1);
	for (int i = 0; i < sze[x]; i++) {
		active[lst[x][i]].erase(x);
		if (active[lst[x][i]].empty()) continue;
		auto g = active[lst[x][i]].lower_bound(x); 
		if (g != active[lst[x][i]].begin()) {
			g--;
			change(*g);
		}
	}
}
int main () {
	for (int i = 1; i < MAXN; i++) sieve[i] = i;
	for (int i = 2; i * i < MAXN; i++) {
		if (sieve[i] == i) for (int j = i; j < MAXN; j += i) sieve[j] = i;
	}
	for (int i = 1; i < MAXN; i++) {
		auto x = get(i);
		sze[i] = x.size();
		for (int j = 0; j < sze[i]; j++) lst[i][j] = x[j];
	}
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	cur.build(1, n, 1);
	while (q--) {
		char z;
		cin >> z;
		if (z == 'S') {
			int x;
			cin >> x;
			if (isactive[x]) {
				deactivate(x);
			} else {
				activate(x);
			}
		} else {
			int l, r;
			cin >> l >> r;
			if (l == r) {
				cout << "NE\n";
				continue;
			}
			if (cur.get(1, n, l, r, 1) <= r) cout << "DA\n";
			else cout << "NE\n";
		}
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70