#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 1e6 + 5;
const int oo32 = 1e9;
#define ALL(a) (a).begin(), (a).end()
int N, Q;
int prime[MAXN];
set<int> save[MAXN];
bool appear[MAXN];
int cur[MAXN];
struct segment_tree {
int N;
int tree[MAXN * 4];
void init(int _N) {
N = _N;
for(int i = 1; i <= 4 * N; i++) tree[i] = oo32;
}
void update(int p, int x) {
int id = 1, l = 1, r = N;
while(l < r) {
int m = (l + r) / 2;
if(p <= m) {
id = id * 2;
r = m;
} else {
id = id * 2 + 1;
l = m + 1;
}
}
tree[id] = x;
while(id >= 1) {
id >>= 1;
tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
}
}
int get(int id, int l, int r, int u, int v) {
if(r < u or l > v) return oo32;
if(u <= l and r <= v) return tree[id];
int m = (l + r) / 2;
return min(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
}
int get(int l, int r) {
return get(1, 1, N, l, r);
}
} ST;
void sieve() {
iota(prime, prime + MAXN + 1, 0);
for(int i = 2; i * i < MAXN; i++) {
if(prime[i] == i) {
for(int j = i * i; j < MAXN; j += i)
prime[j] = i;
}
}
}
void add(int z) {
int x = z;
appear[z] = true;
while(x > 1) {
int p = prime[x];
save[p].emplace(z);
auto low = save[p].lower_bound(z);
if(low != save[p].begin()) {
low--;
if(cur[*low] > z) {
ST.update(*low, z);
cur[*low] = z;
}
}
auto high = save[p].upper_bound(z);
if(high != save[p].end()) {
if(cur[z] > *high) {
ST.update(z, *high);
cur[z] = *high;
}
}
while(x % p == 0) x /= p;
}
}
void del(int x) {
vector<int> temp;
int tmp_x = x;
while (tmp_x > 1) {
int p = prime[tmp_x];
auto it = save[p].lower_bound(x);
if (it != save[p].begin()) {
it--;
if (cur[*it] == x)
temp.push_back(*it);
}
while (tmp_x % p == 0)
tmp_x /= p;
save[p].erase(x);
}
cur[x] = oo32;
ST.update(x, oo32);
sort(ALL(temp));
temp.resize(unique(ALL(temp)) - temp.begin());
for (auto u : temp) {
cur[u] = oo32;
ST.update(u, oo32);
}
for (auto u : temp)
add(u);
appear[x] = false;
}
signed main() {
if(fopen("code.inp", "r")) {
freopen("code.inp", "r", stdin);
freopen("code.out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
sieve();
cin >> N >> Q;
ST.init(N);
for(int i = 0; i < MAXN; i++) cur[i] = oo32;
while(Q--) {
char type;
cin >> type;
if(type == 'S') {
int x;
cin >> x;
if(appear[x] == false)
add(x);
else del(x);
} else {
int l, r;
cin >> l >> r;
int x = ST.get(l, r);
cout << (x <= r ? "DA" : "NE") << "\n";
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | freopen("code.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
124 | freopen("code.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void sieve()':
Main.cpp:54:9: warning: array subscript 1000006 is outside array bounds of 'int [1000005]' [-Warray-bounds]
54 | iota(prime, prime + MAXN + 1, 0);
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:8:5: note: while referencing 'prime'
8 | int prime[MAXN];
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
57176 KB |
Output is correct |
| 2 |
Correct |
9 ms |
57180 KB |
Output is correct |
| 3 |
Correct |
9 ms |
57180 KB |
Output is correct |
| 4 |
Correct |
12 ms |
57180 KB |
Output is correct |
| 5 |
Correct |
9 ms |
57344 KB |
Output is correct |
| 6 |
Correct |
9 ms |
57432 KB |
Output is correct |
| 7 |
Correct |
10 ms |
57180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
65804 KB |
Output is correct |
| 2 |
Correct |
244 ms |
81240 KB |
Output is correct |
| 3 |
Correct |
295 ms |
90704 KB |
Output is correct |
| 4 |
Correct |
15 ms |
59740 KB |
Output is correct |
| 5 |
Correct |
29 ms |
66360 KB |
Output is correct |
| 6 |
Correct |
49 ms |
73168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
57176 KB |
Output is correct |
| 2 |
Correct |
9 ms |
57180 KB |
Output is correct |
| 3 |
Correct |
9 ms |
57180 KB |
Output is correct |
| 4 |
Correct |
12 ms |
57180 KB |
Output is correct |
| 5 |
Correct |
9 ms |
57344 KB |
Output is correct |
| 6 |
Correct |
9 ms |
57432 KB |
Output is correct |
| 7 |
Correct |
10 ms |
57180 KB |
Output is correct |
| 8 |
Correct |
159 ms |
65804 KB |
Output is correct |
| 9 |
Correct |
244 ms |
81240 KB |
Output is correct |
| 10 |
Correct |
295 ms |
90704 KB |
Output is correct |
| 11 |
Correct |
15 ms |
59740 KB |
Output is correct |
| 12 |
Correct |
29 ms |
66360 KB |
Output is correct |
| 13 |
Correct |
49 ms |
73168 KB |
Output is correct |
| 14 |
Correct |
134 ms |
58876 KB |
Output is correct |
| 15 |
Correct |
245 ms |
64268 KB |
Output is correct |
| 16 |
Correct |
341 ms |
93900 KB |
Output is correct |
| 17 |
Correct |
279 ms |
90460 KB |
Output is correct |
| 18 |
Correct |
301 ms |
92212 KB |
Output is correct |
| 19 |
Correct |
348 ms |
92108 KB |
Output is correct |
| 20 |
Correct |
47 ms |
73300 KB |
Output is correct |
| 21 |
Correct |
66 ms |
73300 KB |
Output is correct |
| 22 |
Correct |
48 ms |
73296 KB |
Output is correct |
| 23 |
Correct |
69 ms |
73436 KB |
Output is correct |
