제출 #1144177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144177		0pt1mus23	Radio (COCI22_radio)	C++17	10 / 110	1604 ms	190280 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);
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,b;
    auto it3 = var[n].upper_bound(n);
    if(it3!=var[n].end()){
        mn=*it3;
    }
    for(int x = 2;x*x<=n;x++){
        if(n%x==0){
            auto it = var[x].upper_bound(n);
            if(it!=var[x].end()){
                mn=min(mn,*it);
            }

            b = n/x;
            if(b!=x){
                auto it2 = var[b].upper_bound(n);
                if(it2!=var[b].end()){
                    mn=min(mn,*it2);
                }
            }

        }
    }
    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;
    while(q--){
        char s;
        cin>>s;
        if(s=='S'){
            int n;
            cin>>n;
            sw[n]^=1;
            if(sw[n]){
                // ekle
                for(int i=2;i*i<=n;i++){
                    if(n%i==0){
                        auto it2 = var[i].upper_bound(n);
                        // cout<<n<<" =>"<<i<<endl;
                        if(it2!=var[i].begin()){
                            --it2;
                            // cout<<"sa"<<endl;
                            if(best[*it2]>n){
                                // cout<<n<<" => "<<*it2<<endl;
                                if(best[*it2]!=inf){
                                    lst[best[*it2]].erase(*it2);
                                }
                                best[*it2]=n;
                                lst[n].ins(*it2);
                                st.upd(1,*it2,0,sze,n);
                            }
                        }
                        b =n/i;
                        if(b!=i){
                            auto it= var[b].upper_bound(n);
                            if(it!=var[b].begin()){
                                --it;
                                if(best[*it]>n){
                                    // cout<<n<<" => "<<*it<<endl;
                                    if(best[*it]!=inf){
                                        lst[best[*it]].erase(*it);
                                    }
                                    best[*it]=n;
                                    lst[n].ins(*it);
                                    st.upd(1,*it,0,sze,n);
                                }
                            }
                        }
                    }
                }
                fnd(n);
                var[n].ins(n);
                for(int i=2;i*i<=n;i++){
                    if(n%i==0){
                        var[i].ins(n);
                        b=n/i;
                        if(b!=i){
                            var[b].ins(n);
                        }
                    }
                }
            }
            else{
                if(best[n]!=inf){
                    lst[best[n]].erase(n);
                    best[n]=inf;
                    st.upd(1,n,0,sze,inf);
                }
                var[n].erase(n);
                for(int i=2;i*i<=n;i++){
                    if(n%i==0){
                        var[i].erase(n);
                        b=n/i;
                        if(b!=i){
                            var[b].erase(n);
                        }
                    }
                }
                assert(lst[n].size()<5e2);
                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);
    
    int tt =1;

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

    return 0;
}

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