Submission #879954

#TimeUsernameProblemLanguageResultExecution timeMemory
879954HossamHero7Radio (COCI22_radio)C++14
0 / 110
1555 ms67940 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' const int N = 1e6+5; int spf[N] , isprime[N]; set<int> primes[N]; bool on[N]; int nxt[N] , bef[N]; vector<int> pFactors(int x){ vector<int> tmp; int y = x; while(y != 1){ if(tmp.empty() || tmp.back() != spf[y]) tmp.push_back(spf[y]); y /= spf[y]; } return tmp; } void calc(int x,bool b){ vector<int> tmp = pFactors(x); for(auto p : tmp){ if(!b) primes[p].erase(x); auto it = primes[p].lower_bound(x); if(it != primes[p].end()){ if(b) bef[*it] = max(bef[*it],x); nxt[x] = min(nxt[x] , *it); } if(it != primes[p].begin()){ if(b) nxt[*(--it)] = min(nxt[*it],x); bef[x] = max(bef[x] , *it); } primes[p].insert(x); } } void solve(){ int n,q; cin>>n>>q; for(int i=1;i<N;i++) nxt[i] = 1e9; while(q--){ char c; cin>>c; if(c == 'S'){ int x; cin>>x; if(!on[x]){ calc(x,1); on[x] = 1; } else { on[x] = 0; nxt[x] = 1e9; bef[x] = 0; vector<int> effected; vector<int> tmp = pFactors(x); for(auto p : tmp){ primes[p].erase(x); auto it = primes[p].lower_bound(x); if(it != primes[p].end()) effected.push_back(*it); if(it != primes[p].begin()) effected.push_back(*(--it)); } for(auto y : effected) nxt[y] = 1e9 , bef[y] = -1 , calc(y,0); } } else { int l,r; cin>>l>>r; int mxbef = 0; int mnnxt = 1e9; for(int i=l;i<=r;i++){ mxbef = max(mxbef,bef[i]); mnnxt = min(mnnxt,nxt[i]); } cout<<(mxbef >= l || mnnxt <= r ? "DA" : "NE")<<endl; } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; //cin>>t; memset(isprime,1,sizeof(isprime)); isprime[1] = 0; for(ll i=2;i<N;i++){ if(!isprime[i]) continue; spf[i] = i; for(ll j=i*i;j<N;j+=i){ if(!isprime[j]) continue; spf[j] = i; isprime[j] = 0; } } while(t--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...