Submission #1144181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144181		0pt1mus23	Radio (COCI22_radio)	C++17	110 / 110	983 ms	200300 KiB

Main

#pragma GCC optimize("O1")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
// #define int long long int
#define ins insert
#define pb  push_back
#define pii pair<int,int>
#define endl '\n' 
#define all(x) x.begin(),x.end()

const int mod = 998244353;
const int inf = INT_MAX;
const int LG  = 18;
const int sze = 1e6+23;

struct segtree{
    vector<int>  T;
    segtree(int n){
        T.resize(n*4+23,inf);
    }
    void upd(int node,int idx,int l,int r,int v){
        if(l==r){
            T[node]=v;
            return;
        }
        int mid = (l+r)/2;
        if(idx<=mid){
            upd(2*node,idx,l,mid,v);
        }
        else{
            upd(2*node +1,idx,mid+1,r,v);
        }
        T[node]=min(T[node*2],T[node*2 +1]);
    }
    int qry(int node,int l,int r,int lx,int rx){
        if(rx<l || lx>r){
            return inf;
        }
        if(l<=lx && rx<=r){
            return T[node];
        }
        int mid = (lx+rx)/2;
        return min(qry(2*node,l,r,lx,mid),qry(2*node+1 ,l,r,mid+1,rx));
    }

} st(sze);
vector<int> primes[sze];

set<int> var[sze];
int res[sze];
set<int> lst[sze];
int best[sze];
int sw[sze];
void fnd(int n){
    if(!sw[n]){
        return;
    }
    int mn = inf;
    
    for(auto v:primes[n]){
        auto it = var[v].upper_bound(n);
        if(it!=var[v].end()){
            mn=min(mn,*it);
        }
    }

    if(mn!=inf){
        lst[mn].ins(n);
    }
    best[n]=mn;
    st.upd(1,n,0,sze,mn);
}
void fast(){
    // return;
    int n,q;
    cin>>n>>q;
    for(int i=0;i<=n;i++){
        best[i]=inf;
    }
    int b,x;
    while(q--){
        char s;
        cin>>s;
        if(s=='S'){
            int n;
            cin>>n;
            sw[n]^=1;
            if(sw[n]){
                for(auto v:primes[n]){
                    // cout<<n<<" "<<v<<endl;
                    auto it = var[v].upper_bound(n);
                    if(it!=var[v].begin()){
                        --it;
                        x = *it;
                        // cout<<n<<" => "<<x<<endl;
                        if(best[x]>n){
                            if(best[x]!=inf){
                                lst[best[x]].erase(x);
                            }
                            best[x]=n;
                            lst[n].ins(x);
                            st.upd(1,x,0,sze,n);
                        }
                    }
                }

                fnd(n);
                for(auto v:primes[n]){
                    var[v].ins(n);
                }
            }
            else{
                if(best[n]!=inf){
                    lst[best[n]].erase(n);
                    best[n]=inf;
                    st.upd(1,n,0,sze,inf);
                }
                for(auto v:primes[n]){
                    var[v].erase(n);
                }
                // assert(lst[n].size()<5e1);

                for(auto v:lst[n]){
                    fnd(v);
                }
                lst[n].clear();
            }
        }
        else{
            // qry
            int l,r;
            cin>>l>>r;
            int x = st.qry(1,l,r,0,sze);
            // cout<<l<<" "<<r<<" "<<x<<endl;
            if(x<=r){
                cout<<"DA\n";
            }
            else{
                cout<<"NE\n";
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
        
    for(int i =2;i<sze;i++){
        if(primes[i].empty()){
            for(int j=i;j<sze;j+=i){
                primes[j].pb(i);
            }
        }
    }
    int tt =1;

    // cin>>tt;
    while(tt--){
        fast();
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70