oj.uz

Submission #866701

# Submission time Handle Problem Language Result Execution time Memory
866701 2023-10-26T18:45:25 Z TAhmed33 Radio (COCI22_radio) C++
110 / 110
 581 ms 112684 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 84560 KB Output is correct
2 Correct 95 ms 84544 KB Output is correct
3 Correct 93 ms 84564 KB Output is correct
4 Correct 93 ms 84568 KB Output is correct
5 Correct 95 ms 84572 KB Output is correct
6 Correct 93 ms 84564 KB Output is correct
7 Correct 95 ms 84556 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 90236 KB Output is correct
2 Correct 457 ms 101460 KB Output is correct
3 Correct 523 ms 108368 KB Output is correct
4 Correct 98 ms 84556 KB Output is correct
5 Correct 124 ms 86608 KB Output is correct
6 Correct 185 ms 90460 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 84560 KB Output is correct
2 Correct 95 ms 84544 KB Output is correct
3 Correct 93 ms 84564 KB Output is correct
4 Correct 93 ms 84568 KB Output is correct
5 Correct 95 ms 84572 KB Output is correct
6 Correct 93 ms 84564 KB Output is correct
7 Correct 95 ms 84556 KB Output is correct
8 Correct 276 ms 90236 KB Output is correct
9 Correct 457 ms 101460 KB Output is correct
10 Correct 523 ms 108368 KB Output is correct
11 Correct 98 ms 84556 KB Output is correct
12 Correct 124 ms 86608 KB Output is correct
13 Correct 185 ms 90460 KB Output is correct
14 Correct 239 ms 85904 KB Output is correct
15 Correct 374 ms 89164 KB Output is correct
16 Correct 581 ms 112684 KB Output is correct
17 Correct 461 ms 109132 KB Output is correct
18 Correct 527 ms 111016 KB Output is correct
19 Correct 514 ms 110920 KB Output is correct
20 Correct 157 ms 91988 KB Output is correct
21 Correct 164 ms 91988 KB Output is correct
22 Correct 160 ms 91984 KB Output is correct
23 Correct 164 ms 92144 KB Output is correct