oj.uz

Submission #879954

# Submission time Handle Problem Language Result Execution time Memory
879954 2023-11-28T11:52:15 Z HossamHero7 Radio (COCI22_radio) C++14
0 / 110
 1500 ms 67940 KB 
#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;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 61788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1355 ms 67940 KB Output is correct
2 Execution timed out 1555 ms 67436 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 61788 KB Output isn't correct
2 Halted 0 ms 0 KB -