#include<iostream>
#include<vector>
#include<set>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second
const int MAXN = 1000010, SQ=1010;
int n, q, spf[MAXN], pre[MAXN], pr[MAXN][7], nx[MAXN][7], dii[MAXN][7], tr[2*MAXN];
bool used[MAXN];
set<int> wii[MAXN];
void sieve(){
forsn(i, 2, SQ) if(!spf[i]) {
spf[i]=i;
for(int j=i*i; j<MAXN; j+=i) if(!spf[j]) spf[j]=i;
}
forsn(i, SQ, MAXN) if(!spf[i]) spf[i]=i;
forsn(i, 2, MAXN) pre[i]=i/spf[i];
}
vector<int> divs(int x){
int lst = -1;
vector<int> ret;
while(x>1){
int p = spf[x];
if(lst!=p) ret.PB(lst=p);
x = pre[x];
}
return ret;
}
int query(int l, int r){
int ret = MAXN;
for(l+=n, r+=n; l<r; l>>=1, r>>=1){
if(l&1) ret = min(ret, tr[l++]);
if(r&1) ret = min(ret, tr[--r]);
}
return ret;
}
void modify(int p, int value){
for(tr[p+=n]=value; p>1; p>>=1) tr[p>>1] = min(tr[p], tr[p^1]);
}
void update(int x){
int mn = MAXN;
forn(i, 7) if(dii[x][i]) mn = min(mn, nx[x][i]);
modify(x-1, mn);
}
int main(){
sieve();
scanf("%d %d", &n, &q);
forn(i, 2*n) tr[i] = MAXN;
forn(qnum, q){
char type; scanf(" %c", &type);
if(type == 'S'){
int x; scanf("%d", &x);
if(x==1) continue;
if(used[x]){
for(int i=0; i<7 && dii[x][i]; ++i){
int p = dii[x][i], ba = -1, fo = MAXN;
auto itr = wii[p].find(x);
if(itr != wii[p].begin()) ba = *prev(itr);
if(next(itr) != wii[p].end()) fo = *next(itr);
if(ba != -1){
int j=0;
for(; dii[ba][j] != p; ++j);
nx[ba][j] = fo;
update(ba);
}
if(fo != MAXN){
int j=0;
for(; dii[fo][j] != p; ++j);
pr[fo][j] = ba;
update(fo);
}
wii[p].erase(itr);
}
forn(i, 7) nx[x][i] = MAXN;
forn(i, 7) pr[x][i] = -1;
update(x);
}
else{
if(!dii[x][0]){
vector<int> ds = divs(x);
forn(i, ds.size()) dii[x][i] = ds[i];
}
for(int i=0; i<7 && dii[x][i]; ++i){
int p = dii[x][i];
auto itr = wii[p].insert(x).F;
if(itr == wii[p].begin()) pr[x][i] = -1;
else{
int j=0, val = pr[x][i] = *prev(itr);
for(; dii[val][j] != p; ++j);
nx[val][j] = x;
update(val);
}
if(*itr == *wii[p].rbegin()) nx[x][i]=MAXN;
else{
int j=0, val = nx[x][i] = *next(itr);
for(; dii[val][j] != p; ++j);
pr[val][j] = x;
update(val);
}
}
update(x);
}
used[x]^=1;
}
else{
int l, r; scanf("%d %d", &l, &r);
int mn = query(l-1, r);
printf("%s", mn <= r? "DA\n" : "NE\n");
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:61:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | char type; scanf(" %c", &type);
| ~~~~~^~~~~~~~~~~~~~
Main.cpp:63:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | int x; scanf("%d", &x);
| ~~~~~^~~~~~~~~~
Main.cpp:117:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | int l, r; scanf("%d %d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
55116 KB |
Output is correct |
| 2 |
Correct |
37 ms |
55016 KB |
Output is correct |
| 3 |
Correct |
39 ms |
55116 KB |
Output is correct |
| 4 |
Correct |
37 ms |
55060 KB |
Output is correct |
| 5 |
Correct |
38 ms |
55064 KB |
Output is correct |
| 6 |
Correct |
39 ms |
55024 KB |
Output is correct |
| 7 |
Correct |
37 ms |
55116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
237 ms |
70752 KB |
Output is correct |
| 2 |
Correct |
581 ms |
116708 KB |
Output is correct |
| 3 |
Correct |
726 ms |
165424 KB |
Output is correct |
| 4 |
Correct |
47 ms |
64332 KB |
Output is correct |
| 5 |
Correct |
93 ms |
101276 KB |
Output is correct |
| 6 |
Correct |
155 ms |
147512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
55116 KB |
Output is correct |
| 2 |
Correct |
37 ms |
55016 KB |
Output is correct |
| 3 |
Correct |
39 ms |
55116 KB |
Output is correct |
| 4 |
Correct |
37 ms |
55060 KB |
Output is correct |
| 5 |
Correct |
38 ms |
55064 KB |
Output is correct |
| 6 |
Correct |
39 ms |
55024 KB |
Output is correct |
| 7 |
Correct |
37 ms |
55116 KB |
Output is correct |
| 8 |
Correct |
237 ms |
70752 KB |
Output is correct |
| 9 |
Correct |
581 ms |
116708 KB |
Output is correct |
| 10 |
Correct |
726 ms |
165424 KB |
Output is correct |
| 11 |
Correct |
47 ms |
64332 KB |
Output is correct |
| 12 |
Correct |
93 ms |
101276 KB |
Output is correct |
| 13 |
Correct |
155 ms |
147512 KB |
Output is correct |
| 14 |
Correct |
153 ms |
56812 KB |
Output is correct |
| 15 |
Correct |
258 ms |
64440 KB |
Output is correct |
| 16 |
Correct |
759 ms |
168316 KB |
Output is correct |
| 17 |
Correct |
588 ms |
164812 KB |
Output is correct |
| 18 |
Correct |
670 ms |
166468 KB |
Output is correct |
| 19 |
Correct |
689 ms |
166460 KB |
Output is correct |
| 20 |
Correct |
162 ms |
147532 KB |
Output is correct |
| 21 |
Correct |
157 ms |
147548 KB |
Output is correct |
| 22 |
Correct |
158 ms |
147592 KB |
Output is correct |
| 23 |
Correct |
162 ms |
147544 KB |
Output is correct |
