#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+1, r+=n+1; 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+1]=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, 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);
}
}
}
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);
}
}
else{
int l, r; scanf("%d %d", &l, &r);
int mn = query(l, r+1);
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:113:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | int l, r; scanf("%d %d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
55012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
216 ms |
73628 KB |
Output is correct |
| 2 |
Correct |
485 ms |
118324 KB |
Output is correct |
| 3 |
Correct |
639 ms |
165840 KB |
Output is correct |
| 4 |
Incorrect |
42 ms |
64572 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
55012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
