제출 #852971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
852971		serifefedartar	Radio (COCI22_radio)	C++17	110 / 110	532 ms	89680 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 1e6 + 5;


int n, q;
set<int> prm[MAXN];
int divs[MAXN], on[MAXN]; 
int sg[4*MAXN], ans[MAXN];
void init(int k, int a, int b) {
	if (a == b) {
		sg[k] = 1e9;
		return ;
	}
	init(2*k, a, (a+b)/2);
	init(2*k+1, (a+b)/2+1, b);
	sg[k] = min(sg[2*k], sg[2*k+1]);
}

void update(int k, int a, int b, int plc, int x) {
	if (b < plc || a > plc)
		return ;
	if (a == b) {
		sg[k] = x;
		return ;
	}
	update(2*k, a, (a+b)/2, plc, x);
	update(2*k+1, (a+b)/2+1, b, plc, x);
	sg[k] = min(sg[2*k], sg[2*k+1]);
}

int query(int k, int a, int b, int q_l, int q_r) {
	if (q_r < a || q_l > b)
		return 1e9;
	if (q_l <= a && b <= q_r)
		return sg[k];
	return min(query(2*k, a, (a+b)/2, q_l, q_r), query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}

void activate(int x) {
	int tmp_x = x;
	while (tmp_x > 1) {
		int p = divs[tmp_x];
		prm[p].insert(x);

		auto it = prm[p].lower_bound(x);
		if (it != prm[p].begin()) {
			it--;
			if (ans[*it] > x) {
				update(1, 1, n, *it, x);	
				ans[*it] = x;
			}
		}

		it = prm[p].upper_bound(x);
		if (it != prm[p].end()) {
			if (ans[x] > *it) {
				update(1, 1, n, x, *it);
				ans[x] = *it;
			}
		}

		while (tmp_x % p == 0)
			tmp_x /= p;
	}
	on[x] = true;
}

void deactivate(int x) {
	vector<int> temp;
	int tmp_x = x;
	while (tmp_x > 1) {
		int p = divs[tmp_x];

		auto it = prm[p].lower_bound(x);
		if (it != prm[p].begin()) {
			it--;
			if (ans[*it] == x)
				temp.push_back(*it);
		}

		while (tmp_x % p == 0)
			tmp_x /= p;
		prm[p].erase(x);
	}
	ans[x] = 1e9;
	update(1, 1, n, x, 1e9);

	sort(temp.begin(), temp.end());
	temp.erase(unique(temp.begin(), temp.end()), temp.end());
	for (auto u : temp) {
		ans[u] = 1e9;
		update(1, 1, n, u, 1e9);
	}
	for (auto u : temp)
		activate(u);
	on[x] = false;
}

int main() {
	fast
	cin >> n >> q;

	divs[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (divs[i] == 0) {
			for (int j = i; j <= n; j += i)
				divs[j] = i;
		}
	}
	init(1, 1, n);

	for (int i = 1; i <= n; i++)
		ans[i] = 1e9;

	while (q--) {
		char ch;
		cin >> ch;
		if (ch == 'S') {
			int x;
			cin >> x;
			if (x != 1 && on[x])
				deactivate(x);
			else if (x != 1)
				activate(x);
		} else {
			int l, r;
			cin >> l >> r;
			int q = query(1, 1, n, l, r);
			if (q <= r)
				cout << "DA\n";
			else
				cout << "NE\n";
		}
	}
}

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