oj.uz

Submission #852958

# Submission time Handle Problem Language Result Execution time Memory
852958 2023-09-23T09:17:15 Z serifefedartar Radio (COCI22_radio) C++17
0 / 110
 483 ms 85712 KB 
#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] > ans[*it]) {
				update(1, 1, n, x, ans[*it]);
				ans[x] = ans[*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) {
		update(1, 1, n, u, 1e9);
		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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 52056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 62376 KB Output is correct
2 Correct 336 ms 77136 KB Output is correct
3 Correct 483 ms 85712 KB Output is correct
4 Incorrect 16 ms 56668 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 52056 KB Output isn't correct
2 Halted 0 ms 0 KB -